{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Designing a better simplifier\n",
    "\n",
    "This is a notebook talking through some of the considerations in the design of Hypothesis's approach to simplification.\n",
    "\n",
    "It doesn't perfectly mirror what actually happens in Hypothesis, but it should give some consideration to the sort of things that Hypothesis does and why it takes a particular approach.\n",
    "\n",
    "In order to simplify the scope of this document we are only going to\n",
    "concern ourselves with lists of integers. There are a number of API considerations involved in expanding beyond that point, however most of the algorithmic considerations are the same.\n",
    "\n",
    "The big difference between lists of integers and the general case is that integers can never be too complex. In particular we will rapidly get to the point where individual elements can be simplified in usually only log(n) calls. When dealing with e.g. lists of lists this is a much more complicated proposition. That may be covered in another notebook.\n",
    "\n",
    "Our objective here is to minimize the number of times we check the condition. We won't be looking at actual timing performance, because usually the speed of the condition is the bottleneck there (and where it's not, everything is fast enough that we need not worry)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def greedy_shrink(ls, constraint, shrink):\n",
    "    \"\"\"\n",
    "    This is the \"classic\" QuickCheck algorithm which takes a shrink function\n",
    "    which will iterate over simpler versions of an example. We are trying\n",
    "    to find a local minima: That is an example ls such that condition(ls)\n",
    "    is True but that constraint(t) is False for each t in shrink(ls).\n",
    "    \"\"\"\n",
    "    while True:\n",
    "        for s in shrink(ls):\n",
    "            if constraint(s):\n",
    "                ls = s\n",
    "                break\n",
    "        else:\n",
    "            return ls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def shrink1(ls):\n",
    "    \"\"\"\n",
    "    This is our prototype shrink function. It is very bad. It makes the\n",
    "    mistake of only making very small changes to an example each time.\n",
    "    \n",
    "    Most people write something like this the first time they come to\n",
    "    implement example shrinking. In particular early Hypothesis very much\n",
    "    made this mistake.\n",
    "    \n",
    "    What this does:\n",
    "    \n",
    "    For each index, if the value of the index is non-zero we try\n",
    "    decrementing it by 1.\n",
    "    \n",
    "    We then (regardless of if it's zero) try the list with the value at\n",
    "    that index deleted.\n",
    "    \"\"\"\n",
    "    for i in range(len(ls)):\n",
    "        s = list(ls)\n",
    "        if s[i] > 0:\n",
    "            s[i] -= 1\n",
    "            yield list(s)\n",
    "        del s[i]\n",
    "        yield list(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def show_trace(start, constraint, simplifier):\n",
    "    \"\"\"\n",
    "    This is a debug function. You shouldn't concern yourself with\n",
    "    its implementation too much.\n",
    "    \n",
    "    What it does is print out every intermediate step in applying a\n",
    "    simplifier (a function of the form (list, constraint) -> list)\n",
    "    along with whether it is a successful shrink or not.\n",
    "    \"\"\"\n",
    "    if start is None:\n",
    "        while True:\n",
    "            start = gen_list()\n",
    "            if constraint(start):\n",
    "                break\n",
    "\n",
    "    shrinks = [0]\n",
    "    tests = [0]\n",
    "\n",
    "    def print_shrink(ls):\n",
    "        tests[0] += 1\n",
    "        if constraint(ls):\n",
    "            shrinks[0] += 1\n",
    "            print(\"✓\", ls)\n",
    "            return True\n",
    "        else:\n",
    "            print(\"✗\", ls)\n",
    "        return False\n",
    "    print(\"✓\", start)\n",
    "    simplifier(start, print_shrink)\n",
    "    print()\n",
    "    print(\"%d shrinks with %d function calls\" % (\n",
    "            shrinks[0], tests[0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from functools import partial"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "✓ [5, 5]\n",
      "✓ [4, 5]\n",
      "✓ [3, 5]\n",
      "✓ [2, 5]\n",
      "✓ [1, 5]\n",
      "✓ [0, 5]\n",
      "✗ [5]\n",
      "✓ [0, 4]\n",
      "✗ [4]\n",
      "✓ [0, 3]\n",
      "✗ [3]\n",
      "✓ [0, 2]\n",
      "✗ [2]\n",
      "✓ [0, 1]\n",
      "✗ [1]\n",
      "✓ [0, 0]\n",
      "✗ [0]\n",
      "✗ [0]\n",
      "\n",
      "10 shrinks with 17 function calls\n"
     ]
    }
   ],
   "source": [
    "show_trace([5, 5], lambda x: len(x) >= 2, partial(greedy_shrink, shrink=shrink1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That worked reasonably well, but it sure was a lot of function calls for such a small amount of shrinking. What would have happened if we'd started with [100, 100]?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def shrink2(ls):\n",
    "    \"\"\"\n",
    "    Here is an improved shrink function. We first try deleting each element\n",
    "    and then we try making each element smaller, but we do so from the left\n",
    "    hand side instead of the right. This means we will always find the\n",
    "    smallest value that can go in there, but we will do so much sooner.\n",
    "    \"\"\"\n",
    "    for i in range(len(ls)):\n",
    "        s = list(ls)\n",
    "        del s[i]\n",
    "        yield list(s)\n",
    "        \n",
    "    for i in range(len(ls)):\n",
    "        for x in range(ls[i]):\n",
    "            s = list(ls)\n",
    "            s[i] = x\n",
    "            yield s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "✓ [5, 5]\n",
      "✗ [5]\n",
      "✗ [5]\n",
      "✓ [0, 5]\n",
      "✗ [5]\n",
      "✗ [0]\n",
      "✓ [0, 0]\n",
      "✗ [0]\n",
      "✗ [0]\n",
      "\n",
      "2 shrinks with 8 function calls\n"
     ]
    }
   ],
   "source": [
    "show_trace([5, 5], lambda x: len(x) >= 2, partial(\n",
    "        greedy_shrink, shrink=shrink2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This did indeed reduce the number of function calls significantly - we immediately determine that the value in the cell doesn't matter and we can just put zero there. \n",
    "\n",
    "But what would have happened if the value *did* matter?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "✓ [1000]\n",
      "✗ []\n",
      "✗ [0]\n",
      "✗ [1]\n",
      "✗ [2]\n",
      "✗ [3]\n",
      "✗ [4]\n",
      "✗ [5]\n",
      "✗ [6]\n",
      "✗ [7]\n",
      "✗ [8]\n",
      "✗ [9]\n",
      "✗ [10]\n",
      "✗ [11]\n",
      "✗ [12]\n",
      "✗ [13]\n",
      "✗ [14]\n",
      "✗ [15]\n",
      "✗ [16]\n",
      "✗ [17]\n",
      "✗ [18]\n",
      "✗ [19]\n",
      "✗ [20]\n",
      "✗ [21]\n",
      "✗ [22]\n",
      "✗ [23]\n",
      "✗ [24]\n",
      "✗ [25]\n",
      "✗ [26]\n",
      "✗ [27]\n",
      "✗ [28]\n",
      "✗ [29]\n",
      "✗ [30]\n",
      "✗ [31]\n",
      "✗ [32]\n",
      "✗ [33]\n",
      "✗ [34]\n",
      "✗ [35]\n",
      "✗ [36]\n",
      "✗ [37]\n",
      "✗ [38]\n",
      "✗ [39]\n",
      "✗ [40]\n",
      "✗ [41]\n",
      "✗ [42]\n",
      "✗ [43]\n",
      "✗ [44]\n",
      "✗ [45]\n",
      "✗ [46]\n",
      "✗ [47]\n",
      "✗ [48]\n",
      "✗ [49]\n",
      "✗ [50]\n",
      "✗ [51]\n",
      "✗ [52]\n",
      "✗ [53]\n",
      "✗ [54]\n",
      "✗ [55]\n",
      "✗ [56]\n",
      "✗ [57]\n",
      "✗ [58]\n",
      "✗ [59]\n",
      "✗ [60]\n",
      "✗ [61]\n",
      "✗ [62]\n",
      "✗ [63]\n",
      "✗ [64]\n",
      "✗ [65]\n",
      "✗ [66]\n",
      "✗ [67]\n",
      "✗ [68]\n",
      "✗ [69]\n",
      "✗ [70]\n",
      "✗ [71]\n",
      "✗ [72]\n",
      "✗ [73]\n",
      "✗ [74]\n",
      "✗ [75]\n",
      "✗ [76]\n",
      "✗ [77]\n",
      "✗ [78]\n",
      "✗ [79]\n",
      "✗ [80]\n",
      "✗ [81]\n",
      "✗ [82]\n",
      "✗ [83]\n",
      "✗ [84]\n",
      "✗ [85]\n",
      "✗ [86]\n",
      "✗ [87]\n",
      "✗ [88]\n",
      "✗ [89]\n",
      "✗ [90]\n",
      "✗ [91]\n",
      "✗ [92]\n",
      "✗ [93]\n",
      "✗ [94]\n",
      "✗ [95]\n",
      "✗ [96]\n",
      "✗ [97]\n",
      "✗ [98]\n",
      "✗ [99]\n",
      "✗ [100]\n",
      "✗ [101]\n",
      "✗ [102]\n",
      "✗ [103]\n",
      "✗ [104]\n",
      "✗ [105]\n",
      "✗ [106]\n",
      "✗ [107]\n",
      "✗ [108]\n",
      "✗ [109]\n",
      "✗ [110]\n",
      "✗ [111]\n",
      "✗ [112]\n",
      "✗ [113]\n",
      "✗ [114]\n",
      "✗ [115]\n",
      "✗ [116]\n",
      "✗ [117]\n",
      "✗ [118]\n",
      "✗ [119]\n",
      "✗ [120]\n",
      "✗ [121]\n",
      "✗ [122]\n",
      "✗ [123]\n",
      "✗ [124]\n",
      "✗ [125]\n",
      "✗ [126]\n",
      "✗ [127]\n",
      "✗ [128]\n",
      "✗ [129]\n",
      "✗ [130]\n",
      "✗ [131]\n",
      "✗ [132]\n",
      "✗ [133]\n",
      "✗ [134]\n",
      "✗ [135]\n",
      "✗ [136]\n",
      "✗ [137]\n",
      "✗ [138]\n",
      "✗ [139]\n",
      "✗ [140]\n",
      "✗ [141]\n",
      "✗ [142]\n",
      "✗ [143]\n",
      "✗ [144]\n",
      "✗ [145]\n",
      "✗ [146]\n",
      "✗ [147]\n",
      "✗ [148]\n",
      "✗ [149]\n",
      "✗ [150]\n",
      "✗ [151]\n",
      "✗ [152]\n",
      "✗ [153]\n",
      "✗ [154]\n",
      "✗ [155]\n",
      "✗ [156]\n",
      "✗ [157]\n",
      "✗ [158]\n",
      "✗ [159]\n",
      "✗ [160]\n",
      "✗ [161]\n",
      "✗ [162]\n",
      "✗ [163]\n",
      "✗ [164]\n",
      "✗ [165]\n",
      "✗ [166]\n",
      "✗ [167]\n",
      "✗ [168]\n",
      "✗ [169]\n",
      "✗ [170]\n",
      "✗ [171]\n",
      "✗ [172]\n",
      "✗ [173]\n",
      "✗ [174]\n",
      "✗ [175]\n",
      "✗ [176]\n",
      "✗ [177]\n",
      "✗ [178]\n",
      "✗ [179]\n",
      "✗ [180]\n",
      "✗ [181]\n",
      "✗ [182]\n",
      "✗ [183]\n",
      "✗ [184]\n",
      "✗ [185]\n",
      "✗ [186]\n",
      "✗ [187]\n",
      "✗ [188]\n",
      "✗ [189]\n",
      "✗ [190]\n",
      "✗ [191]\n",
      "✗ [192]\n",
      "✗ [193]\n",
      "✗ [194]\n",
      "✗ [195]\n",
      "✗ [196]\n",
      "✗ [197]\n",
      "✗ [198]\n",
      "✗ [199]\n",
      "✗ [200]\n",
      "✗ [201]\n",
      "✗ [202]\n",
      "✗ [203]\n",
      "✗ [204]\n",
      "✗ [205]\n",
      "✗ [206]\n",
      "✗ [207]\n",
      "✗ [208]\n",
      "✗ [209]\n",
      "✗ [210]\n",
      "✗ [211]\n",
      "✗ [212]\n",
      "✗ [213]\n",
      "✗ [214]\n",
      "✗ [215]\n",
      "✗ [216]\n",
      "✗ [217]\n",
      "✗ [218]\n",
      "✗ [219]\n",
      "✗ [220]\n",
      "✗ [221]\n",
      "✗ [222]\n",
      "✗ [223]\n",
      "✗ [224]\n",
      "✗ [225]\n",
      "✗ [226]\n",
      "✗ [227]\n",
      "✗ [228]\n",
      "✗ [229]\n",
      "✗ [230]\n",
      "✗ [231]\n",
      "✗ [232]\n",
      "✗ [233]\n",
      "✗ [234]\n",
      "✗ [235]\n",
      "✗ [236]\n",
      "✗ [237]\n",
      "✗ [238]\n",
      "✗ [239]\n",
      "✗ [240]\n",
      "✗ [241]\n",
      "✗ [242]\n",
      "✗ [243]\n",
      "✗ [244]\n",
      "✗ [245]\n",
      "✗ [246]\n",
      "✗ [247]\n",
      "✗ [248]\n",
      "✗ [249]\n",
      "✗ [250]\n",
      "✗ [251]\n",
      "✗ [252]\n",
      "✗ [253]\n",
      "✗ [254]\n",
      "✗ [255]\n",
      "✗ [256]\n",
      "✗ [257]\n",
      "✗ [258]\n",
      "✗ [259]\n",
      "✗ [260]\n",
      "✗ [261]\n",
      "✗ [262]\n",
      "✗ [263]\n",
      "✗ [264]\n",
      "✗ [265]\n",
      "✗ [266]\n",
      "✗ [267]\n",
      "✗ [268]\n",
      "✗ [269]\n",
      "✗ [270]\n",
      "✗ [271]\n",
      "✗ [272]\n",
      "✗ [273]\n",
      "✗ [274]\n",
      "✗ [275]\n",
      "✗ [276]\n",
      "✗ [277]\n",
      "✗ [278]\n",
      "✗ [279]\n",
      "✗ [280]\n",
      "✗ [281]\n",
      "✗ [282]\n",
      "✗ [283]\n",
      "✗ [284]\n",
      "✗ [285]\n",
      "✗ [286]\n",
      "✗ [287]\n",
      "✗ [288]\n",
      "✗ [289]\n",
      "✗ [290]\n",
      "✗ [291]\n",
      "✗ [292]\n",
      "✗ [293]\n",
      "✗ [294]\n",
      "✗ [295]\n",
      "✗ [296]\n",
      "✗ [297]\n",
      "✗ [298]\n",
      "✗ [299]\n",
      "✗ [300]\n",
      "✗ [301]\n",
      "✗ [302]\n",
      "✗ [303]\n",
      "✗ [304]\n",
      "✗ [305]\n",
      "✗ [306]\n",
      "✗ [307]\n",
      "✗ [308]\n",
      "✗ [309]\n",
      "✗ [310]\n",
      "✗ [311]\n",
      "✗ [312]\n",
      "✗ [313]\n",
      "✗ [314]\n",
      "✗ [315]\n",
      "✗ [316]\n",
      "✗ [317]\n",
      "✗ [318]\n",
      "✗ [319]\n",
      "✗ [320]\n",
      "✗ [321]\n",
      "✗ [322]\n",
      "✗ [323]\n",
      "✗ [324]\n",
      "✗ [325]\n",
      "✗ [326]\n",
      "✗ [327]\n",
      "✗ [328]\n",
      "✗ [329]\n",
      "✗ [330]\n",
      "✗ [331]\n",
      "✗ [332]\n",
      "✗ [333]\n",
      "✗ [334]\n",
      "✗ [335]\n",
      "✗ [336]\n",
      "✗ [337]\n",
      "✗ [338]\n",
      "✗ [339]\n",
      "✗ [340]\n",
      "✗ [341]\n",
      "✗ [342]\n",
      "✗ [343]\n",
      "✗ [344]\n",
      "✗ [345]\n",
      "✗ [346]\n",
      "✗ [347]\n",
      "✗ [348]\n",
      "✗ [349]\n",
      "✗ [350]\n",
      "✗ [351]\n",
      "✗ [352]\n",
      "✗ [353]\n",
      "✗ [354]\n",
      "✗ [355]\n",
      "✗ [356]\n",
      "✗ [357]\n",
      "✗ [358]\n",
      "✗ [359]\n",
      "✗ [360]\n",
      "✗ [361]\n",
      "✗ [362]\n",
      "✗ [363]\n",
      "✗ [364]\n",
      "✗ [365]\n",
      "✗ [366]\n",
      "✗ [367]\n",
      "✗ [368]\n",
      "✗ [369]\n",
      "✗ [370]\n",
      "✗ [371]\n",
      "✗ [372]\n",
      "✗ [373]\n",
      "✗ [374]\n",
      "✗ [375]\n",
      "✗ [376]\n",
      "✗ [377]\n",
      "✗ [378]\n",
      "✗ [379]\n",
      "✗ [380]\n",
      "✗ [381]\n",
      "✗ [382]\n",
      "✗ [383]\n",
      "✗ [384]\n",
      "✗ [385]\n",
      "✗ [386]\n",
      "✗ [387]\n",
      "✗ [388]\n",
      "✗ [389]\n",
      "✗ [390]\n",
      "✗ [391]\n",
      "✗ [392]\n",
      "✗ [393]\n",
      "✗ [394]\n",
      "✗ [395]\n",
      "✗ [396]\n",
      "✗ [397]\n",
      "✗ [398]\n",
      "✗ [399]\n",
      "✗ [400]\n",
      "✗ [401]\n",
      "✗ [402]\n",
      "✗ [403]\n",
      "✗ [404]\n",
      "✗ [405]\n",
      "✗ [406]\n",
      "✗ [407]\n",
      "✗ [408]\n",
      "✗ [409]\n",
      "✗ [410]\n",
      "✗ [411]\n",
      "✗ [412]\n",
      "✗ [413]\n",
      "✗ [414]\n",
      "✗ [415]\n",
      "✗ [416]\n",
      "✗ [417]\n",
      "✗ [418]\n",
      "✗ [419]\n",
      "✗ [420]\n",
      "✗ [421]\n",
      "✗ [422]\n",
      "✗ [423]\n",
      "✗ [424]\n",
      "✗ [425]\n",
      "✗ [426]\n",
      "✗ [427]\n",
      "✗ [428]\n",
      "✗ [429]\n",
      "✗ [430]\n",
      "✗ [431]\n",
      "✗ [432]\n",
      "✗ [433]\n",
      "✗ [434]\n",
      "✗ [435]\n",
      "✗ [436]\n",
      "✗ [437]\n",
      "✗ [438]\n",
      "✗ [439]\n",
      "✗ [440]\n",
      "✗ [441]\n",
      "✗ [442]\n",
      "✗ [443]\n",
      "✗ [444]\n",
      "✗ [445]\n",
      "✗ [446]\n",
      "✗ [447]\n",
      "✗ [448]\n",
      "✗ [449]\n",
      "✗ [450]\n",
      "✗ [451]\n",
      "✗ [452]\n",
      "✗ [453]\n",
      "✗ [454]\n",
      "✗ [455]\n",
      "✗ [456]\n",
      "✗ [457]\n",
      "✗ [458]\n",
      "✗ [459]\n",
      "✗ [460]\n",
      "✗ [461]\n",
      "✗ [462]\n",
      "✗ [463]\n",
      "✗ [464]\n",
      "✗ [465]\n",
      "✗ [466]\n",
      "✗ [467]\n",
      "✗ [468]\n",
      "✗ [469]\n",
      "✗ [470]\n",
      "✗ [471]\n",
      "✗ [472]\n",
      "✗ [473]\n",
      "✗ [474]\n",
      "✗ [475]\n",
      "✗ [476]\n",
      "✗ [477]\n",
      "✗ [478]\n",
      "✗ [479]\n",
      "✗ [480]\n",
      "✗ [481]\n",
      "✗ [482]\n",
      "✗ [483]\n",
      "✗ [484]\n",
      "✗ [485]\n",
      "✗ [486]\n",
      "✗ [487]\n",
      "✗ [488]\n",
      "✗ [489]\n",
      "✗ [490]\n",
      "✗ [491]\n",
      "✗ [492]\n",
      "✗ [493]\n",
      "✗ [494]\n",
      "✗ [495]\n",
      "✗ [496]\n",
      "✗ [497]\n",
      "✗ [498]\n",
      "✗ [499]\n",
      "✓ [500]\n",
      "✗ []\n",
      "✗ [0]\n",
      "✗ [1]\n",
      "✗ [2]\n",
      "✗ [3]\n",
      "✗ [4]\n",
      "✗ [5]\n",
      "✗ [6]\n",
      "✗ [7]\n",
      "✗ [8]\n",
      "✗ [9]\n",
      "✗ [10]\n",
      "✗ [11]\n",
      "✗ [12]\n",
      "✗ [13]\n",
      "✗ [14]\n",
      "✗ [15]\n",
      "✗ [16]\n",
      "✗ [17]\n",
      "✗ [18]\n",
      "✗ [19]\n",
      "✗ [20]\n",
      "✗ [21]\n",
      "✗ [22]\n",
      "✗ [23]\n",
      "✗ [24]\n",
      "✗ [25]\n",
      "✗ [26]\n",
      "✗ [27]\n",
      "✗ [28]\n",
      "✗ [29]\n",
      "✗ [30]\n",
      "✗ [31]\n",
      "✗ [32]\n",
      "✗ [33]\n",
      "✗ [34]\n",
      "✗ [35]\n",
      "✗ [36]\n",
      "✗ [37]\n",
      "✗ [38]\n",
      "✗ [39]\n",
      "✗ [40]\n",
      "✗ [41]\n",
      "✗ [42]\n",
      "✗ [43]\n",
      "✗ [44]\n",
      "✗ [45]\n",
      "✗ [46]\n",
      "✗ [47]\n",
      "✗ [48]\n",
      "✗ [49]\n",
      "✗ [50]\n",
      "✗ [51]\n",
      "✗ [52]\n",
      "✗ [53]\n",
      "✗ [54]\n",
      "✗ [55]\n",
      "✗ [56]\n",
      "✗ [57]\n",
      "✗ [58]\n",
      "✗ [59]\n",
      "✗ [60]\n",
      "✗ [61]\n",
      "✗ [62]\n",
      "✗ [63]\n",
      "✗ [64]\n",
      "✗ [65]\n",
      "✗ [66]\n",
      "✗ [67]\n",
      "✗ [68]\n",
      "✗ [69]\n",
      "✗ [70]\n",
      "✗ [71]\n",
      "✗ [72]\n",
      "✗ [73]\n",
      "✗ [74]\n",
      "✗ [75]\n",
      "✗ [76]\n",
      "✗ [77]\n",
      "✗ [78]\n",
      "✗ [79]\n",
      "✗ [80]\n",
      "✗ [81]\n",
      "✗ [82]\n",
      "✗ [83]\n",
      "✗ [84]\n",
      "✗ [85]\n",
      "✗ [86]\n",
      "✗ [87]\n",
      "✗ [88]\n",
      "✗ [89]\n",
      "✗ [90]\n",
      "✗ [91]\n",
      "✗ [92]\n",
      "✗ [93]\n",
      "✗ [94]\n",
      "✗ [95]\n",
      "✗ [96]\n",
      "✗ [97]\n",
      "✗ [98]\n",
      "✗ [99]\n",
      "✗ [100]\n",
      "✗ [101]\n",
      "✗ [102]\n",
      "✗ [103]\n",
      "✗ [104]\n",
      "✗ [105]\n",
      "✗ [106]\n",
      "✗ [107]\n",
      "✗ [108]\n",
      "✗ [109]\n",
      "✗ [110]\n",
      "✗ [111]\n",
      "✗ [112]\n",
      "✗ [113]\n",
      "✗ [114]\n",
      "✗ [115]\n",
      "✗ [116]\n",
      "✗ [117]\n",
      "✗ [118]\n",
      "✗ [119]\n",
      "✗ [120]\n",
      "✗ [121]\n",
      "✗ [122]\n",
      "✗ [123]\n",
      "✗ [124]\n",
      "✗ [125]\n",
      "✗ [126]\n",
      "✗ [127]\n",
      "✗ [128]\n",
      "✗ [129]\n",
      "✗ [130]\n",
      "✗ [131]\n",
      "✗ [132]\n",
      "✗ [133]\n",
      "✗ [134]\n",
      "✗ [135]\n",
      "✗ [136]\n",
      "✗ [137]\n",
      "✗ [138]\n",
      "✗ [139]\n",
      "✗ [140]\n",
      "✗ [141]\n",
      "✗ [142]\n",
      "✗ [143]\n",
      "✗ [144]\n",
      "✗ [145]\n",
      "✗ [146]\n",
      "✗ [147]\n",
      "✗ [148]\n",
      "✗ [149]\n",
      "✗ [150]\n",
      "✗ [151]\n",
      "✗ [152]\n",
      "✗ [153]\n",
      "✗ [154]\n",
      "✗ [155]\n",
      "✗ [156]\n",
      "✗ [157]\n",
      "✗ [158]\n",
      "✗ [159]\n",
      "✗ [160]\n",
      "✗ [161]\n",
      "✗ [162]\n",
      "✗ [163]\n",
      "✗ [164]\n",
      "✗ [165]\n",
      "✗ [166]\n",
      "✗ [167]\n",
      "✗ [168]\n",
      "✗ [169]\n",
      "✗ [170]\n",
      "✗ [171]\n",
      "✗ [172]\n",
      "✗ [173]\n",
      "✗ [174]\n",
      "✗ [175]\n",
      "✗ [176]\n",
      "✗ [177]\n",
      "✗ [178]\n",
      "✗ [179]\n",
      "✗ [180]\n",
      "✗ [181]\n",
      "✗ [182]\n",
      "✗ [183]\n",
      "✗ [184]\n",
      "✗ [185]\n",
      "✗ [186]\n",
      "✗ [187]\n",
      "✗ [188]\n",
      "✗ [189]\n",
      "✗ [190]\n",
      "✗ [191]\n",
      "✗ [192]\n",
      "✗ [193]\n",
      "✗ [194]\n",
      "✗ [195]\n",
      "✗ [196]\n",
      "✗ [197]\n",
      "✗ [198]\n",
      "✗ [199]\n",
      "✗ [200]\n",
      "✗ [201]\n",
      "✗ [202]\n",
      "✗ [203]\n",
      "✗ [204]\n",
      "✗ [205]\n",
      "✗ [206]\n",
      "✗ [207]\n",
      "✗ [208]\n",
      "✗ [209]\n",
      "✗ [210]\n",
      "✗ [211]\n",
      "✗ [212]\n",
      "✗ [213]\n",
      "✗ [214]\n",
      "✗ [215]\n",
      "✗ [216]\n",
      "✗ [217]\n",
      "✗ [218]\n",
      "✗ [219]\n",
      "✗ [220]\n",
      "✗ [221]\n",
      "✗ [222]\n",
      "✗ [223]\n",
      "✗ [224]\n",
      "✗ [225]\n",
      "✗ [226]\n",
      "✗ [227]\n",
      "✗ [228]\n",
      "✗ [229]\n",
      "✗ [230]\n",
      "✗ [231]\n",
      "✗ [232]\n",
      "✗ [233]\n",
      "✗ [234]\n",
      "✗ [235]\n",
      "✗ [236]\n",
      "✗ [237]\n",
      "✗ [238]\n",
      "✗ [239]\n",
      "✗ [240]\n",
      "✗ [241]\n",
      "✗ [242]\n",
      "✗ [243]\n",
      "✗ [244]\n",
      "✗ [245]\n",
      "✗ [246]\n",
      "✗ [247]\n",
      "✗ [248]\n",
      "✗ [249]\n",
      "✗ [250]\n",
      "✗ [251]\n",
      "✗ [252]\n",
      "✗ [253]\n",
      "✗ [254]\n",
      "✗ [255]\n",
      "✗ [256]\n",
      "✗ [257]\n",
      "✗ [258]\n",
      "✗ [259]\n",
      "✗ [260]\n",
      "✗ [261]\n",
      "✗ [262]\n",
      "✗ [263]\n",
      "✗ [264]\n",
      "✗ [265]\n",
      "✗ [266]\n",
      "✗ [267]\n",
      "✗ [268]\n",
      "✗ [269]\n",
      "✗ [270]\n",
      "✗ [271]\n",
      "✗ [272]\n",
      "✗ [273]\n",
      "✗ [274]\n",
      "✗ [275]\n",
      "✗ [276]\n",
      "✗ [277]\n",
      "✗ [278]\n",
      "✗ [279]\n",
      "✗ [280]\n",
      "✗ [281]\n",
      "✗ [282]\n",
      "✗ [283]\n",
      "✗ [284]\n",
      "✗ [285]\n",
      "✗ [286]\n",
      "✗ [287]\n",
      "✗ [288]\n",
      "✗ [289]\n",
      "✗ [290]\n",
      "✗ [291]\n",
      "✗ [292]\n",
      "✗ [293]\n",
      "✗ [294]\n",
      "✗ [295]\n",
      "✗ [296]\n",
      "✗ [297]\n",
      "✗ [298]\n",
      "✗ [299]\n",
      "✗ [300]\n",
      "✗ [301]\n",
      "✗ [302]\n",
      "✗ [303]\n",
      "✗ [304]\n",
      "✗ [305]\n",
      "✗ [306]\n",
      "✗ [307]\n",
      "✗ [308]\n",
      "✗ [309]\n",
      "✗ [310]\n",
      "✗ [311]\n",
      "✗ [312]\n",
      "✗ [313]\n",
      "✗ [314]\n",
      "✗ [315]\n",
      "✗ [316]\n",
      "✗ [317]\n",
      "✗ [318]\n",
      "✗ [319]\n",
      "✗ [320]\n",
      "✗ [321]\n",
      "✗ [322]\n",
      "✗ [323]\n",
      "✗ [324]\n",
      "✗ [325]\n",
      "✗ [326]\n",
      "✗ [327]\n",
      "✗ [328]\n",
      "✗ [329]\n",
      "✗ [330]\n",
      "✗ [331]\n",
      "✗ [332]\n",
      "✗ [333]\n",
      "✗ [334]\n",
      "✗ [335]\n",
      "✗ [336]\n",
      "✗ [337]\n",
      "✗ [338]\n",
      "✗ [339]\n",
      "✗ [340]\n",
      "✗ [341]\n",
      "✗ [342]\n",
      "✗ [343]\n",
      "✗ [344]\n",
      "✗ [345]\n",
      "✗ [346]\n",
      "✗ [347]\n",
      "✗ [348]\n",
      "✗ [349]\n",
      "✗ [350]\n",
      "✗ [351]\n",
      "✗ [352]\n",
      "✗ [353]\n",
      "✗ [354]\n",
      "✗ [355]\n",
      "✗ [356]\n",
      "✗ [357]\n",
      "✗ [358]\n",
      "✗ [359]\n",
      "✗ [360]\n",
      "✗ [361]\n",
      "✗ [362]\n",
      "✗ [363]\n",
      "✗ [364]\n",
      "✗ [365]\n",
      "✗ [366]\n",
      "✗ [367]\n",
      "✗ [368]\n",
      "✗ [369]\n",
      "✗ [370]\n",
      "✗ [371]\n",
      "✗ [372]\n",
      "✗ [373]\n",
      "✗ [374]\n",
      "✗ [375]\n",
      "✗ [376]\n",
      "✗ [377]\n",
      "✗ [378]\n",
      "✗ [379]\n",
      "✗ [380]\n",
      "✗ [381]\n",
      "✗ [382]\n",
      "✗ [383]\n",
      "✗ [384]\n",
      "✗ [385]\n",
      "✗ [386]\n",
      "✗ [387]\n",
      "✗ [388]\n",
      "✗ [389]\n",
      "✗ [390]\n",
      "✗ [391]\n",
      "✗ [392]\n",
      "✗ [393]\n",
      "✗ [394]\n",
      "✗ [395]\n",
      "✗ [396]\n",
      "✗ [397]\n",
      "✗ [398]\n",
      "✗ [399]\n",
      "✗ [400]\n",
      "✗ [401]\n",
      "✗ [402]\n",
      "✗ [403]\n",
      "✗ [404]\n",
      "✗ [405]\n",
      "✗ [406]\n",
      "✗ [407]\n",
      "✗ [408]\n",
      "✗ [409]\n",
      "✗ [410]\n",
      "✗ [411]\n",
      "✗ [412]\n",
      "✗ [413]\n",
      "✗ [414]\n",
      "✗ [415]\n",
      "✗ [416]\n",
      "✗ [417]\n",
      "✗ [418]\n",
      "✗ [419]\n",
      "✗ [420]\n",
      "✗ [421]\n",
      "✗ [422]\n",
      "✗ [423]\n",
      "✗ [424]\n",
      "✗ [425]\n",
      "✗ [426]\n",
      "✗ [427]\n",
      "✗ [428]\n",
      "✗ [429]\n",
      "✗ [430]\n",
      "✗ [431]\n",
      "✗ [432]\n",
      "✗ [433]\n",
      "✗ [434]\n",
      "✗ [435]\n",
      "✗ [436]\n",
      "✗ [437]\n",
      "✗ [438]\n",
      "✗ [439]\n",
      "✗ [440]\n",
      "✗ [441]\n",
      "✗ [442]\n",
      "✗ [443]\n",
      "✗ [444]\n",
      "✗ [445]\n",
      "✗ [446]\n",
      "✗ [447]\n",
      "✗ [448]\n",
      "✗ [449]\n",
      "✗ [450]\n",
      "✗ [451]\n",
      "✗ [452]\n",
      "✗ [453]\n",
      "✗ [454]\n",
      "✗ [455]\n",
      "✗ [456]\n",
      "✗ [457]\n",
      "✗ [458]\n",
      "✗ [459]\n",
      "✗ [460]\n",
      "✗ [461]\n",
      "✗ [462]\n",
      "✗ [463]\n",
      "✗ [464]\n",
      "✗ [465]\n",
      "✗ [466]\n",
      "✗ [467]\n",
      "✗ [468]\n",
      "✗ [469]\n",
      "✗ [470]\n",
      "✗ [471]\n",
      "✗ [472]\n",
      "✗ [473]\n",
      "✗ [474]\n",
      "✗ [475]\n",
      "✗ [476]\n",
      "✗ [477]\n",
      "✗ [478]\n",
      "✗ [479]\n",
      "✗ [480]\n",
      "✗ [481]\n",
      "✗ [482]\n",
      "✗ [483]\n",
      "✗ [484]\n",
      "✗ [485]\n",
      "✗ [486]\n",
      "✗ [487]\n",
      "✗ [488]\n",
      "✗ [489]\n",
      "✗ [490]\n",
      "✗ [491]\n",
      "✗ [492]\n",
      "✗ [493]\n",
      "✗ [494]\n",
      "✗ [495]\n",
      "✗ [496]\n",
      "✗ [497]\n",
      "✗ [498]\n",
      "✗ [499]\n",
      "\n",
      "1 shrinks with 1003 function calls\n"
     ]
    }
   ],
   "source": [
    "show_trace([1000], lambda x: sum(x) >= 500,\n",
    "           partial(greedy_shrink, shrink=shrink2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Because we're trying every intermediate value, what we have amounts to a linear probe up to the smallest value that will work. If that smallest value is large, this will take a long time. Our shrinking is still O(n), but n is now the size of the smallest value that will work rather than the starting value. This is still pretty suboptimal.\n",
    "\n",
    "What we want to do is try to replace our linear probe with a binary search. What we'll get isn't exactly a binary search, but it's close enough."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def shrink_integer(n):\n",
    "    \"\"\"\n",
    "    Shrinker for individual integers.\n",
    "    \n",
    "    What happens is that we start from the left, first probing upwards in powers of two.\n",
    "    \n",
    "    When this would take us past our target value we then binary chop towards it.\n",
    "    \"\"\"\n",
    "    if not n:\n",
    "        return\n",
    "    for k in range(64):\n",
    "        probe = 2 ** k\n",
    "        if probe >= n:\n",
    "            break\n",
    "        yield probe - 1\n",
    "    probe //= 2\n",
    "    while True:\n",
    "        probe = (probe + n) // 2\n",
    "        yield probe\n",
    "        if probe == n - 1:\n",
    "            break\n",
    "\n",
    "\n",
    "def shrink3(ls):\n",
    "    for i in range(len(ls)):\n",
    "        s = list(ls)\n",
    "        del s[i]\n",
    "        yield list(s)\n",
    "        for x in shrink_integer(ls[i]):\n",
    "            s = list(ls)\n",
    "            s[i] = x\n",
    "            yield s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 3, 7, 15, 31, 63, 127, 255, 378, 439, 469, 484, 492, 496, 498, 499]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(shrink_integer(500))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This gives us a reasonable distribution of O(log(n)) values in the middle while still making sure we start with 0 and finish with n - 1.\n",
    "\n",
    "In Hypothesis's actual implementation we also try random values in the probe region in case there's something special about things near powers of two, but we won't worry about that here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "✓ [1000]\n",
      "✗ []\n",
      "✗ [0]\n",
      "✗ [1]\n",
      "✗ [3]\n",
      "✗ [7]\n",
      "✗ [15]\n",
      "✗ [31]\n",
      "✗ [63]\n",
      "✗ [127]\n",
      "✗ [255]\n",
      "✓ [511]\n",
      "✗ []\n",
      "✗ [0]\n",
      "✗ [1]\n",
      "✗ [3]\n",
      "✗ [7]\n",
      "✗ [15]\n",
      "✗ [31]\n",
      "✗ [63]\n",
      "✗ [127]\n",
      "✗ [255]\n",
      "✗ [383]\n",
      "✗ [447]\n",
      "✗ [479]\n",
      "✗ [495]\n",
      "✓ [503]\n",
      "✗ []\n",
      "✗ [0]\n",
      "✗ [1]\n",
      "✗ [3]\n",
      "✗ [7]\n",
      "✗ [15]\n",
      "✗ [31]\n",
      "✗ [63]\n",
      "✗ [127]\n",
      "✗ [255]\n",
      "✗ [379]\n",
      "✗ [441]\n",
      "✗ [472]\n",
      "✗ [487]\n",
      "✗ [495]\n",
      "✗ [499]\n",
      "✓ [501]\n",
      "✗ []\n",
      "✗ [0]\n",
      "✗ [1]\n",
      "✗ [3]\n",
      "✗ [7]\n",
      "✗ [15]\n",
      "✗ [31]\n",
      "✗ [63]\n",
      "✗ [127]\n",
      "✗ [255]\n",
      "✗ [378]\n",
      "✗ [439]\n",
      "✗ [470]\n",
      "✗ [485]\n",
      "✗ [493]\n",
      "✗ [497]\n",
      "✗ [499]\n",
      "✓ [500]\n",
      "✗ []\n",
      "✗ [0]\n",
      "✗ [1]\n",
      "✗ [3]\n",
      "✗ [7]\n",
      "✗ [15]\n",
      "✗ [31]\n",
      "✗ [63]\n",
      "✗ [127]\n",
      "✗ [255]\n",
      "✗ [378]\n",
      "✗ [439]\n",
      "✗ [469]\n",
      "✗ [484]\n",
      "✗ [492]\n",
      "✗ [496]\n",
      "✗ [498]\n",
      "✗ [499]\n",
      "\n",
      "4 shrinks with 79 function calls\n"
     ]
    }
   ],
   "source": [
    "show_trace([1000], lambda x: sum(x) >= 500, partial(\n",
    "        greedy_shrink, shrink=shrink3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This now runs in a much more reasonable number of function calls.\n",
    "\n",
    "Now we want to look at how to reduce the number of elements in the list more efficiently. We're currently making the same mistake we did with n umbers. Only reducing one at a time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "✓ [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✓ [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✓ [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✓ [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✓ [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✓ [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✓ [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✓ [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✓ [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✓ [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✓ [2, 2, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✓ [2, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✓ [2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✓ [2, 2, 2, 2, 2, 2, 2]\n",
      "✓ [2, 2, 2, 2, 2, 2]\n",
      "✓ [2, 2, 2, 2, 2]\n",
      "✓ [2, 2, 2, 2]\n",
      "✓ [2, 2, 2]\n",
      "✓ [2, 2]\n",
      "✗ [2]\n",
      "✗ [0, 2]\n",
      "✓ [1, 2]\n",
      "✗ [2]\n",
      "✗ [0, 2]\n",
      "✗ [1]\n",
      "✗ [1, 0]\n",
      "✗ [1, 1]\n",
      "\n",
      "19 shrinks with 26 function calls\n"
     ]
    }
   ],
   "source": [
    "show_trace([2] * 20, lambda x: sum(x) >= 3, partial(\n",
    "        greedy_shrink, shrink=shrink3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We won't try too hard here, because typically our lists are not *that* long. We will just attempt to start by finding a shortish initial prefix that demonstrates the behaviour:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def shrink_to_prefix(ls):\n",
    "    i = 1\n",
    "    while i < len(ls):\n",
    "        yield ls[:i]\n",
    "        i *= 2\n",
    "\n",
    "\n",
    "def delete_individual_elements(ls):\n",
    "    for i in range(len(ls)):\n",
    "        s = list(ls)\n",
    "        del s[i]\n",
    "        yield list(s)\n",
    "\n",
    "\n",
    "def shrink_individual_elements(ls):\n",
    "    for i in range(len(ls)):\n",
    "        for x in shrink_integer(ls[i]):\n",
    "            s = list(ls)\n",
    "            s[i] = x\n",
    "            yield s\n",
    "            \n",
    "def shrink4(ls):\n",
    "    yield from shrink_to_prefix(ls)\n",
    "    yield from delete_individual_elements(ls)\n",
    "    yield from shrink_individual_elements(ls)            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "✓ [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✗ [2]\n",
      "✓ [2, 2]\n",
      "✗ [2]\n",
      "✗ [2]\n",
      "✗ [2]\n",
      "✗ [0, 2]\n",
      "✓ [1, 2]\n",
      "✗ [1]\n",
      "✗ [2]\n",
      "✗ [1]\n",
      "✗ [0, 2]\n",
      "✗ [1, 0]\n",
      "✗ [1, 1]\n",
      "\n",
      "2 shrinks with 13 function calls\n"
     ]
    }
   ],
   "source": [
    "show_trace([2] * 20, lambda x: sum(x) >= 3, partial(\n",
    "        greedy_shrink, shrink=shrink4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The problem we now want to address is the fact that when we're shrinking elements we're only shrinking them one at a time. This means that even though we're only O(log(k)) in each element, we're O(log(k)^n) in the whole list where n is the length of the list. For even very modest k this is bad.\n",
    "\n",
    "In general we may not be able to fix this, but in practice for a lot of common structures we can exploit similarity to try to do simultaneous shrinking.\n",
    "\n",
    "Here is our starting example: We start and finish with all identical values. We would like to be able to shortcut through a lot of the uninteresting intermediate examples somehow."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "✓ [20, 20, 20, 20, 20, 20, 20]\n",
      "✗ [20]\n",
      "✗ [20, 20]\n",
      "✗ [20, 20, 20, 20]\n",
      "✓ [20, 20, 20, 20, 20, 20]\n",
      "✗ [20]\n",
      "✗ [20, 20]\n",
      "✗ [20, 20, 20, 20]\n",
      "✓ [20, 20, 20, 20, 20]\n",
      "✗ [20]\n",
      "✗ [20, 20]\n",
      "✗ [20, 20, 20, 20]\n",
      "✗ [20, 20, 20, 20]\n",
      "✗ [20, 20, 20, 20]\n",
      "✗ [20, 20, 20, 20]\n",
      "✗ [20, 20, 20, 20]\n",
      "✗ [20, 20, 20, 20]\n",
      "✗ [0, 20, 20, 20, 20]\n",
      "✗ [1, 20, 20, 20, 20]\n",
      "✗ [3, 20, 20, 20, 20]\n",
      "✓ [7, 20, 20, 20, 20]\n",
      "✗ [7]\n",
      "✗ [7, 20]\n",
      "✗ [7, 20, 20, 20]\n",
      "✗ [20, 20, 20, 20]\n",
      "✗ [7, 20, 20, 20]\n",
      "✗ [7, 20, 20, 20]\n",
      "✗ [7, 20, 20, 20]\n",
      "✗ [7, 20, 20, 20]\n",
      "✗ [0, 20, 20, 20, 20]\n",
      "✗ [1, 20, 20, 20, 20]\n",
      "✗ [3, 20, 20, 20, 20]\n",
      "✓ [5, 20, 20, 20, 20]\n",
      "✗ [5]\n",
      "✗ [5, 20]\n",
      "✗ [5, 20, 20, 20]\n",
      "✗ [20, 20, 20, 20]\n",
      "✗ [5, 20, 20, 20]\n",
      "✗ [5, 20, 20, 20]\n",
      "✗ [5, 20, 20, 20]\n",
      "✗ [5, 20, 20, 20]\n",
      "✗ [0, 20, 20, 20, 20]\n",
      "✗ [1, 20, 20, 20, 20]\n",
      "✗ [3, 20, 20, 20, 20]\n",
      "✗ [4, 20, 20, 20, 20]\n",
      "✗ [5, 0, 20, 20, 20]\n",
      "✗ [5, 1, 20, 20, 20]\n",
      "✗ [5, 3, 20, 20, 20]\n",
      "✓ [5, 7, 20, 20, 20]\n",
      "✗ [5]\n",
      "✗ [5, 7]\n",
      "✗ [5, 7, 20, 20]\n",
      "✗ [7, 20, 20, 20]\n",
      "✗ [5, 20, 20, 20]\n",
      "✗ [5, 7, 20, 20]\n",
      "✗ [5, 7, 20, 20]\n",
      "✗ [5, 7, 20, 20]\n",
      "✗ [0, 7, 20, 20, 20]\n",
      "✗ [1, 7, 20, 20, 20]\n",
      "✗ [3, 7, 20, 20, 20]\n",
      "✗ [4, 7, 20, 20, 20]\n",
      "✗ [5, 0, 20, 20, 20]\n",
      "✗ [5, 1, 20, 20, 20]\n",
      "✗ [5, 3, 20, 20, 20]\n",
      "✓ [5, 5, 20, 20, 20]\n",
      "✗ [5]\n",
      "✗ [5, 5]\n",
      "✗ [5, 5, 20, 20]\n",
      "✗ [5, 20, 20, 20]\n",
      "✗ [5, 20, 20, 20]\n",
      "✗ [5, 5, 20, 20]\n",
      "✗ [5, 5, 20, 20]\n",
      "✗ [5, 5, 20, 20]\n",
      "✗ [0, 5, 20, 20, 20]\n",
      "✗ [1, 5, 20, 20, 20]\n",
      "✗ [3, 5, 20, 20, 20]\n",
      "✗ [4, 5, 20, 20, 20]\n",
      "✗ [5, 0, 20, 20, 20]\n",
      "✗ [5, 1, 20, 20, 20]\n",
      "✗ [5, 3, 20, 20, 20]\n",
      "✗ [5, 4, 20, 20, 20]\n",
      "✗ [5, 5, 0, 20, 20]\n",
      "✗ [5, 5, 1, 20, 20]\n",
      "✗ [5, 5, 3, 20, 20]\n",
      "✓ [5, 5, 7, 20, 20]\n",
      "✗ [5]\n",
      "✗ [5, 5]\n",
      "✗ [5, 5, 7, 20]\n",
      "✗ [5, 7, 20, 20]\n",
      "✗ [5, 7, 20, 20]\n",
      "✗ [5, 5, 20, 20]\n",
      "✗ [5, 5, 7, 20]\n",
      "✗ [5, 5, 7, 20]\n",
      "✗ [0, 5, 7, 20, 20]\n",
      "✗ [1, 5, 7, 20, 20]\n",
      "✗ [3, 5, 7, 20, 20]\n",
      "✗ [4, 5, 7, 20, 20]\n",
      "✗ [5, 0, 7, 20, 20]\n",
      "✗ [5, 1, 7, 20, 20]\n",
      "✗ [5, 3, 7, 20, 20]\n",
      "✗ [5, 4, 7, 20, 20]\n",
      "✗ [5, 5, 0, 20, 20]\n",
      "✗ [5, 5, 1, 20, 20]\n",
      "✗ [5, 5, 3, 20, 20]\n",
      "✓ [5, 5, 5, 20, 20]\n",
      "✗ [5]\n",
      "✗ [5, 5]\n",
      "✗ [5, 5, 5, 20]\n",
      "✗ [5, 5, 20, 20]\n",
      "✗ [5, 5, 20, 20]\n",
      "✗ [5, 5, 20, 20]\n",
      "✗ [5, 5, 5, 20]\n",
      "✗ [5, 5, 5, 20]\n",
      "✗ [0, 5, 5, 20, 20]\n",
      "✗ [1, 5, 5, 20, 20]\n",
      "✗ [3, 5, 5, 20, 20]\n",
      "✗ [4, 5, 5, 20, 20]\n",
      "✗ [5, 0, 5, 20, 20]\n",
      "✗ [5, 1, 5, 20, 20]\n",
      "✗ [5, 3, 5, 20, 20]\n",
      "✗ [5, 4, 5, 20, 20]\n",
      "✗ [5, 5, 0, 20, 20]\n",
      "✗ [5, 5, 1, 20, 20]\n",
      "✗ [5, 5, 3, 20, 20]\n",
      "✗ [5, 5, 4, 20, 20]\n",
      "✗ [5, 5, 5, 0, 20]\n",
      "✗ [5, 5, 5, 1, 20]\n",
      "✗ [5, 5, 5, 3, 20]\n",
      "✓ [5, 5, 5, 7, 20]\n",
      "✗ [5]\n",
      "✗ [5, 5]\n",
      "✗ [5, 5, 5, 7]\n",
      "✗ [5, 5, 7, 20]\n",
      "✗ [5, 5, 7, 20]\n",
      "✗ [5, 5, 7, 20]\n",
      "✗ [5, 5, 5, 20]\n",
      "✗ [5, 5, 5, 7]\n",
      "✗ [0, 5, 5, 7, 20]\n",
      "✗ [1, 5, 5, 7, 20]\n",
      "✗ [3, 5, 5, 7, 20]\n",
      "✗ [4, 5, 5, 7, 20]\n",
      "✗ [5, 0, 5, 7, 20]\n",
      "✗ [5, 1, 5, 7, 20]\n",
      "✗ [5, 3, 5, 7, 20]\n",
      "✗ [5, 4, 5, 7, 20]\n",
      "✗ [5, 5, 0, 7, 20]\n",
      "✗ [5, 5, 1, 7, 20]\n",
      "✗ [5, 5, 3, 7, 20]\n",
      "✗ [5, 5, 4, 7, 20]\n",
      "✗ [5, 5, 5, 0, 20]\n",
      "✗ [5, 5, 5, 1, 20]\n",
      "✗ [5, 5, 5, 3, 20]\n",
      "✓ [5, 5, 5, 5, 20]\n",
      "✗ [5]\n",
      "✗ [5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [5, 5, 5, 20]\n",
      "✗ [5, 5, 5, 20]\n",
      "✗ [5, 5, 5, 20]\n",
      "✗ [5, 5, 5, 20]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [0, 5, 5, 5, 20]\n",
      "✗ [1, 5, 5, 5, 20]\n",
      "✗ [3, 5, 5, 5, 20]\n",
      "✗ [4, 5, 5, 5, 20]\n",
      "✗ [5, 0, 5, 5, 20]\n",
      "✗ [5, 1, 5, 5, 20]\n",
      "✗ [5, 3, 5, 5, 20]\n",
      "✗ [5, 4, 5, 5, 20]\n",
      "✗ [5, 5, 0, 5, 20]\n",
      "✗ [5, 5, 1, 5, 20]\n",
      "✗ [5, 5, 3, 5, 20]\n",
      "✗ [5, 5, 4, 5, 20]\n",
      "✗ [5, 5, 5, 0, 20]\n",
      "✗ [5, 5, 5, 1, 20]\n",
      "✗ [5, 5, 5, 3, 20]\n",
      "✗ [5, 5, 5, 4, 20]\n",
      "✗ [5, 5, 5, 5, 0]\n",
      "✗ [5, 5, 5, 5, 1]\n",
      "✗ [5, 5, 5, 5, 3]\n",
      "✓ [5, 5, 5, 5, 7]\n",
      "✗ [5]\n",
      "✗ [5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [5, 5, 5, 7]\n",
      "✗ [5, 5, 5, 7]\n",
      "✗ [5, 5, 5, 7]\n",
      "✗ [5, 5, 5, 7]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [0, 5, 5, 5, 7]\n",
      "✗ [1, 5, 5, 5, 7]\n",
      "✗ [3, 5, 5, 5, 7]\n",
      "✗ [4, 5, 5, 5, 7]\n",
      "✗ [5, 0, 5, 5, 7]\n",
      "✗ [5, 1, 5, 5, 7]\n",
      "✗ [5, 3, 5, 5, 7]\n",
      "✗ [5, 4, 5, 5, 7]\n",
      "✗ [5, 5, 0, 5, 7]\n",
      "✗ [5, 5, 1, 5, 7]\n",
      "✗ [5, 5, 3, 5, 7]\n",
      "✗ [5, 5, 4, 5, 7]\n",
      "✗ [5, 5, 5, 0, 7]\n",
      "✗ [5, 5, 5, 1, 7]\n",
      "✗ [5, 5, 5, 3, 7]\n",
      "✗ [5, 5, 5, 4, 7]\n",
      "✗ [5, 5, 5, 5, 0]\n",
      "✗ [5, 5, 5, 5, 1]\n",
      "✗ [5, 5, 5, 5, 3]\n",
      "✓ [5, 5, 5, 5, 5]\n",
      "✗ [5]\n",
      "✗ [5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [0, 5, 5, 5, 5]\n",
      "✗ [1, 5, 5, 5, 5]\n",
      "✗ [3, 5, 5, 5, 5]\n",
      "✗ [4, 5, 5, 5, 5]\n",
      "✗ [5, 0, 5, 5, 5]\n",
      "✗ [5, 1, 5, 5, 5]\n",
      "✗ [5, 3, 5, 5, 5]\n",
      "✗ [5, 4, 5, 5, 5]\n",
      "✗ [5, 5, 0, 5, 5]\n",
      "✗ [5, 5, 1, 5, 5]\n",
      "✗ [5, 5, 3, 5, 5]\n",
      "✗ [5, 5, 4, 5, 5]\n",
      "✗ [5, 5, 5, 0, 5]\n",
      "✗ [5, 5, 5, 1, 5]\n",
      "✗ [5, 5, 5, 3, 5]\n",
      "✗ [5, 5, 5, 4, 5]\n",
      "✗ [5, 5, 5, 5, 0]\n",
      "✗ [5, 5, 5, 5, 1]\n",
      "✗ [5, 5, 5, 5, 3]\n",
      "✗ [5, 5, 5, 5, 4]\n",
      "\n",
      "12 shrinks with 236 function calls\n"
     ]
    }
   ],
   "source": [
    "show_trace([20] * 7,\n",
    "           lambda x: len([t for t in x if t >= 5]) >= 5,\n",
    "           partial(greedy_shrink, shrink=shrink4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def shrink_shared(ls):\n",
    "    \"\"\"\n",
    "    Look for all sets of shared indices and try to perform a simultaneous shrink on\n",
    "    their value, replacing all of them at once.\n",
    "    \n",
    "    In actual Hypothesis we also try replacing only subsets of the values when there\n",
    "    are more than two shared values, but we won't worry about that here.\n",
    "    \"\"\"\n",
    "    shared_indices = {}\n",
    "    for i in range(len(ls)):\n",
    "        shared_indices.setdefault(ls[i], []).append(i)\n",
    "    for sharing in shared_indices.values():\n",
    "        if len(sharing) > 1:\n",
    "            for v in shrink_integer(ls[sharing[0]]):\n",
    "                s = list(ls)\n",
    "                for i in sharing:\n",
    "                    s[i] = v\n",
    "                yield s\n",
    "\n",
    "\n",
    "def shrink5(ls):\n",
    "    yield from shrink_to_prefix(ls)\n",
    "    yield from delete_individual_elements(ls)\n",
    "    yield from shrink_shared(ls)\n",
    "    yield from shrink_individual_elements(ls)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "✓ [20, 20, 20, 20, 20, 20, 20]\n",
      "✗ [20]\n",
      "✗ [20, 20]\n",
      "✗ [20, 20, 20, 20]\n",
      "✓ [20, 20, 20, 20, 20, 20]\n",
      "✗ [20]\n",
      "✗ [20, 20]\n",
      "✗ [20, 20, 20, 20]\n",
      "✓ [20, 20, 20, 20, 20]\n",
      "✗ [20]\n",
      "✗ [20, 20]\n",
      "✗ [20, 20, 20, 20]\n",
      "✗ [20, 20, 20, 20]\n",
      "✗ [20, 20, 20, 20]\n",
      "✗ [20, 20, 20, 20]\n",
      "✗ [20, 20, 20, 20]\n",
      "✗ [20, 20, 20, 20]\n",
      "✗ [0, 0, 0, 0, 0]\n",
      "✗ [1, 1, 1, 1, 1]\n",
      "✗ [3, 3, 3, 3, 3]\n",
      "✓ [7, 7, 7, 7, 7]\n",
      "✗ [7]\n",
      "✗ [7, 7]\n",
      "✗ [7, 7, 7, 7]\n",
      "✗ [7, 7, 7, 7]\n",
      "✗ [7, 7, 7, 7]\n",
      "✗ [7, 7, 7, 7]\n",
      "✗ [7, 7, 7, 7]\n",
      "✗ [7, 7, 7, 7]\n",
      "✗ [0, 0, 0, 0, 0]\n",
      "✗ [1, 1, 1, 1, 1]\n",
      "✗ [3, 3, 3, 3, 3]\n",
      "✓ [5, 5, 5, 5, 5]\n",
      "✗ [5]\n",
      "✗ [5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [0, 0, 0, 0, 0]\n",
      "✗ [1, 1, 1, 1, 1]\n",
      "✗ [3, 3, 3, 3, 3]\n",
      "✗ [4, 4, 4, 4, 4]\n",
      "✗ [0, 5, 5, 5, 5]\n",
      "✗ [1, 5, 5, 5, 5]\n",
      "✗ [3, 5, 5, 5, 5]\n",
      "✗ [4, 5, 5, 5, 5]\n",
      "✗ [5, 0, 5, 5, 5]\n",
      "✗ [5, 1, 5, 5, 5]\n",
      "✗ [5, 3, 5, 5, 5]\n",
      "✗ [5, 4, 5, 5, 5]\n",
      "✗ [5, 5, 0, 5, 5]\n",
      "✗ [5, 5, 1, 5, 5]\n",
      "✗ [5, 5, 3, 5, 5]\n",
      "✗ [5, 5, 4, 5, 5]\n",
      "✗ [5, 5, 5, 0, 5]\n",
      "✗ [5, 5, 5, 1, 5]\n",
      "✗ [5, 5, 5, 3, 5]\n",
      "✗ [5, 5, 5, 4, 5]\n",
      "✗ [5, 5, 5, 5, 0]\n",
      "✗ [5, 5, 5, 5, 1]\n",
      "✗ [5, 5, 5, 5, 3]\n",
      "✗ [5, 5, 5, 5, 4]\n",
      "\n",
      "4 shrinks with 64 function calls\n"
     ]
    }
   ],
   "source": [
    "show_trace([20] * 7,\n",
    "           lambda x: len([t for t in x if t >= 5]) >= 5,\n",
    "           partial(greedy_shrink, shrink=shrink5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This achieves the desired result. We rapidly progress through all of the intermediate stages. We do still have to perform individual shrinks at the end unfortunately (this is unavoidable), but the size of the elements is much smaller now so it takes less time.\n",
    "\n",
    "Unfortunately while this solves the problem in this case it's almost useless, because unless you find yourself in the exact right starting position it never does anything."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "✓ [20, 21, 22, 23, 24, 25, 26]\n",
      "✗ [20]\n",
      "✗ [20, 21]\n",
      "✗ [20, 21, 22, 23]\n",
      "✓ [21, 22, 23, 24, 25, 26]\n",
      "✗ [21]\n",
      "✗ [21, 22]\n",
      "✗ [21, 22, 23, 24]\n",
      "✓ [22, 23, 24, 25, 26]\n",
      "✗ [22]\n",
      "✗ [22, 23]\n",
      "✗ [22, 23, 24, 25]\n",
      "✗ [23, 24, 25, 26]\n",
      "✗ [22, 24, 25, 26]\n",
      "✗ [22, 23, 25, 26]\n",
      "✗ [22, 23, 24, 26]\n",
      "✗ [22, 23, 24, 25]\n",
      "✗ [0, 23, 24, 25, 26]\n",
      "✗ [1, 23, 24, 25, 26]\n",
      "✗ [3, 23, 24, 25, 26]\n",
      "✓ [7, 23, 24, 25, 26]\n",
      "✗ [7]\n",
      "✗ [7, 23]\n",
      "✗ [7, 23, 24, 25]\n",
      "✗ [23, 24, 25, 26]\n",
      "✗ [7, 24, 25, 26]\n",
      "✗ [7, 23, 25, 26]\n",
      "✗ [7, 23, 24, 26]\n",
      "✗ [7, 23, 24, 25]\n",
      "✗ [0, 23, 24, 25, 26]\n",
      "✗ [1, 23, 24, 25, 26]\n",
      "✗ [3, 23, 24, 25, 26]\n",
      "✓ [5, 23, 24, 25, 26]\n",
      "✗ [5]\n",
      "✗ [5, 23]\n",
      "✗ [5, 23, 24, 25]\n",
      "✗ [23, 24, 25, 26]\n",
      "✗ [5, 24, 25, 26]\n",
      "✗ [5, 23, 25, 26]\n",
      "✗ [5, 23, 24, 26]\n",
      "✗ [5, 23, 24, 25]\n",
      "✗ [0, 23, 24, 25, 26]\n",
      "✗ [1, 23, 24, 25, 26]\n",
      "✗ [3, 23, 24, 25, 26]\n",
      "✗ [4, 23, 24, 25, 26]\n",
      "✗ [5, 0, 24, 25, 26]\n",
      "✗ [5, 1, 24, 25, 26]\n",
      "✗ [5, 3, 24, 25, 26]\n",
      "✓ [5, 7, 24, 25, 26]\n",
      "✗ [5]\n",
      "✗ [5, 7]\n",
      "✗ [5, 7, 24, 25]\n",
      "✗ [7, 24, 25, 26]\n",
      "✗ [5, 24, 25, 26]\n",
      "✗ [5, 7, 25, 26]\n",
      "✗ [5, 7, 24, 26]\n",
      "✗ [5, 7, 24, 25]\n",
      "✗ [0, 7, 24, 25, 26]\n",
      "✗ [1, 7, 24, 25, 26]\n",
      "✗ [3, 7, 24, 25, 26]\n",
      "✗ [4, 7, 24, 25, 26]\n",
      "✗ [5, 0, 24, 25, 26]\n",
      "✗ [5, 1, 24, 25, 26]\n",
      "✗ [5, 3, 24, 25, 26]\n",
      "✓ [5, 5, 24, 25, 26]\n",
      "✗ [5]\n",
      "✗ [5, 5]\n",
      "✗ [5, 5, 24, 25]\n",
      "✗ [5, 24, 25, 26]\n",
      "✗ [5, 24, 25, 26]\n",
      "✗ [5, 5, 25, 26]\n",
      "✗ [5, 5, 24, 26]\n",
      "✗ [5, 5, 24, 25]\n",
      "✗ [0, 0, 24, 25, 26]\n",
      "✗ [1, 1, 24, 25, 26]\n",
      "✗ [3, 3, 24, 25, 26]\n",
      "✗ [4, 4, 24, 25, 26]\n",
      "✗ [0, 5, 24, 25, 26]\n",
      "✗ [1, 5, 24, 25, 26]\n",
      "✗ [3, 5, 24, 25, 26]\n",
      "✗ [4, 5, 24, 25, 26]\n",
      "✗ [5, 0, 24, 25, 26]\n",
      "✗ [5, 1, 24, 25, 26]\n",
      "✗ [5, 3, 24, 25, 26]\n",
      "✗ [5, 4, 24, 25, 26]\n",
      "✗ [5, 5, 0, 25, 26]\n",
      "✗ [5, 5, 1, 25, 26]\n",
      "✗ [5, 5, 3, 25, 26]\n",
      "✓ [5, 5, 7, 25, 26]\n",
      "✗ [5]\n",
      "✗ [5, 5]\n",
      "✗ [5, 5, 7, 25]\n",
      "✗ [5, 7, 25, 26]\n",
      "✗ [5, 7, 25, 26]\n",
      "✗ [5, 5, 25, 26]\n",
      "✗ [5, 5, 7, 26]\n",
      "✗ [5, 5, 7, 25]\n",
      "✗ [0, 0, 7, 25, 26]\n",
      "✗ [1, 1, 7, 25, 26]\n",
      "✗ [3, 3, 7, 25, 26]\n",
      "✗ [4, 4, 7, 25, 26]\n",
      "✗ [0, 5, 7, 25, 26]\n",
      "✗ [1, 5, 7, 25, 26]\n",
      "✗ [3, 5, 7, 25, 26]\n",
      "✗ [4, 5, 7, 25, 26]\n",
      "✗ [5, 0, 7, 25, 26]\n",
      "✗ [5, 1, 7, 25, 26]\n",
      "✗ [5, 3, 7, 25, 26]\n",
      "✗ [5, 4, 7, 25, 26]\n",
      "✗ [5, 5, 0, 25, 26]\n",
      "✗ [5, 5, 1, 25, 26]\n",
      "✗ [5, 5, 3, 25, 26]\n",
      "✓ [5, 5, 5, 25, 26]\n",
      "✗ [5]\n",
      "✗ [5, 5]\n",
      "✗ [5, 5, 5, 25]\n",
      "✗ [5, 5, 25, 26]\n",
      "✗ [5, 5, 25, 26]\n",
      "✗ [5, 5, 25, 26]\n",
      "✗ [5, 5, 5, 26]\n",
      "✗ [5, 5, 5, 25]\n",
      "✗ [0, 0, 0, 25, 26]\n",
      "✗ [1, 1, 1, 25, 26]\n",
      "✗ [3, 3, 3, 25, 26]\n",
      "✗ [4, 4, 4, 25, 26]\n",
      "✗ [0, 5, 5, 25, 26]\n",
      "✗ [1, 5, 5, 25, 26]\n",
      "✗ [3, 5, 5, 25, 26]\n",
      "✗ [4, 5, 5, 25, 26]\n",
      "✗ [5, 0, 5, 25, 26]\n",
      "✗ [5, 1, 5, 25, 26]\n",
      "✗ [5, 3, 5, 25, 26]\n",
      "✗ [5, 4, 5, 25, 26]\n",
      "✗ [5, 5, 0, 25, 26]\n",
      "✗ [5, 5, 1, 25, 26]\n",
      "✗ [5, 5, 3, 25, 26]\n",
      "✗ [5, 5, 4, 25, 26]\n",
      "✗ [5, 5, 5, 0, 26]\n",
      "✗ [5, 5, 5, 1, 26]\n",
      "✗ [5, 5, 5, 3, 26]\n",
      "✓ [5, 5, 5, 7, 26]\n",
      "✗ [5]\n",
      "✗ [5, 5]\n",
      "✗ [5, 5, 5, 7]\n",
      "✗ [5, 5, 7, 26]\n",
      "✗ [5, 5, 7, 26]\n",
      "✗ [5, 5, 7, 26]\n",
      "✗ [5, 5, 5, 26]\n",
      "✗ [5, 5, 5, 7]\n",
      "✗ [0, 0, 0, 7, 26]\n",
      "✗ [1, 1, 1, 7, 26]\n",
      "✗ [3, 3, 3, 7, 26]\n",
      "✗ [4, 4, 4, 7, 26]\n",
      "✗ [0, 5, 5, 7, 26]\n",
      "✗ [1, 5, 5, 7, 26]\n",
      "✗ [3, 5, 5, 7, 26]\n",
      "✗ [4, 5, 5, 7, 26]\n",
      "✗ [5, 0, 5, 7, 26]\n",
      "✗ [5, 1, 5, 7, 26]\n",
      "✗ [5, 3, 5, 7, 26]\n",
      "✗ [5, 4, 5, 7, 26]\n",
      "✗ [5, 5, 0, 7, 26]\n",
      "✗ [5, 5, 1, 7, 26]\n",
      "✗ [5, 5, 3, 7, 26]\n",
      "✗ [5, 5, 4, 7, 26]\n",
      "✗ [5, 5, 5, 0, 26]\n",
      "✗ [5, 5, 5, 1, 26]\n",
      "✗ [5, 5, 5, 3, 26]\n",
      "✓ [5, 5, 5, 5, 26]\n",
      "✗ [5]\n",
      "✗ [5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [5, 5, 5, 26]\n",
      "✗ [5, 5, 5, 26]\n",
      "✗ [5, 5, 5, 26]\n",
      "✗ [5, 5, 5, 26]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [0, 0, 0, 0, 26]\n",
      "✗ [1, 1, 1, 1, 26]\n",
      "✗ [3, 3, 3, 3, 26]\n",
      "✗ [4, 4, 4, 4, 26]\n",
      "✗ [0, 5, 5, 5, 26]\n",
      "✗ [1, 5, 5, 5, 26]\n",
      "✗ [3, 5, 5, 5, 26]\n",
      "✗ [4, 5, 5, 5, 26]\n",
      "✗ [5, 0, 5, 5, 26]\n",
      "✗ [5, 1, 5, 5, 26]\n",
      "✗ [5, 3, 5, 5, 26]\n",
      "✗ [5, 4, 5, 5, 26]\n",
      "✗ [5, 5, 0, 5, 26]\n",
      "✗ [5, 5, 1, 5, 26]\n",
      "✗ [5, 5, 3, 5, 26]\n",
      "✗ [5, 5, 4, 5, 26]\n",
      "✗ [5, 5, 5, 0, 26]\n",
      "✗ [5, 5, 5, 1, 26]\n",
      "✗ [5, 5, 5, 3, 26]\n",
      "✗ [5, 5, 5, 4, 26]\n",
      "✗ [5, 5, 5, 5, 0]\n",
      "✗ [5, 5, 5, 5, 1]\n",
      "✗ [5, 5, 5, 5, 3]\n",
      "✓ [5, 5, 5, 5, 7]\n",
      "✗ [5]\n",
      "✗ [5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [5, 5, 5, 7]\n",
      "✗ [5, 5, 5, 7]\n",
      "✗ [5, 5, 5, 7]\n",
      "✗ [5, 5, 5, 7]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [0, 0, 0, 0, 7]\n",
      "✗ [1, 1, 1, 1, 7]\n",
      "✗ [3, 3, 3, 3, 7]\n",
      "✗ [4, 4, 4, 4, 7]\n",
      "✗ [0, 5, 5, 5, 7]\n",
      "✗ [1, 5, 5, 5, 7]\n",
      "✗ [3, 5, 5, 5, 7]\n",
      "✗ [4, 5, 5, 5, 7]\n",
      "✗ [5, 0, 5, 5, 7]\n",
      "✗ [5, 1, 5, 5, 7]\n",
      "✗ [5, 3, 5, 5, 7]\n",
      "✗ [5, 4, 5, 5, 7]\n",
      "✗ [5, 5, 0, 5, 7]\n",
      "✗ [5, 5, 1, 5, 7]\n",
      "✗ [5, 5, 3, 5, 7]\n",
      "✗ [5, 5, 4, 5, 7]\n",
      "✗ [5, 5, 5, 0, 7]\n",
      "✗ [5, 5, 5, 1, 7]\n",
      "✗ [5, 5, 5, 3, 7]\n",
      "✗ [5, 5, 5, 4, 7]\n",
      "✗ [5, 5, 5, 5, 0]\n",
      "✗ [5, 5, 5, 5, 1]\n",
      "✗ [5, 5, 5, 5, 3]\n",
      "✓ [5, 5, 5, 5, 5]\n",
      "✗ [5]\n",
      "✗ [5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [0, 0, 0, 0, 0]\n",
      "✗ [1, 1, 1, 1, 1]\n",
      "✗ [3, 3, 3, 3, 3]\n",
      "✗ [4, 4, 4, 4, 4]\n",
      "✗ [0, 5, 5, 5, 5]\n",
      "✗ [1, 5, 5, 5, 5]\n",
      "✗ [3, 5, 5, 5, 5]\n",
      "✗ [4, 5, 5, 5, 5]\n",
      "✗ [5, 0, 5, 5, 5]\n",
      "✗ [5, 1, 5, 5, 5]\n",
      "✗ [5, 3, 5, 5, 5]\n",
      "✗ [5, 4, 5, 5, 5]\n",
      "✗ [5, 5, 0, 5, 5]\n",
      "✗ [5, 5, 1, 5, 5]\n",
      "✗ [5, 5, 3, 5, 5]\n",
      "✗ [5, 5, 4, 5, 5]\n",
      "✗ [5, 5, 5, 0, 5]\n",
      "✗ [5, 5, 5, 1, 5]\n",
      "✗ [5, 5, 5, 3, 5]\n",
      "✗ [5, 5, 5, 4, 5]\n",
      "✗ [5, 5, 5, 5, 0]\n",
      "✗ [5, 5, 5, 5, 1]\n",
      "✗ [5, 5, 5, 5, 3]\n",
      "✗ [5, 5, 5, 5, 4]\n",
      "\n",
      "12 shrinks with 264 function calls\n"
     ]
    }
   ],
   "source": [
    "show_trace([20 + i for i in range(7)],\n",
    "           lambda x: len([t for t in x if t >= 5]) >= 5,\n",
    "           partial(greedy_shrink, shrink=shrink5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So what we're going to try to do is to try a simplification first which *creates* that exact right starting condition. Further it's one that will be potentially very useful even if we don't actually have the situation where we have shared shrinks.\n",
    "\n",
    "What we're going to do is we're going to use values from the list to act as evidence for how complex things need to be. Starting from the smallest, we'll try capping the array at each individual value and see what happens.\n",
    "\n",
    "As well as being potentially a very rapid shrink, this creates lists with lots of duplicates, which enables the simultaneous shrinking to shine."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def replace_with_simpler(ls):\n",
    "    if not ls:\n",
    "        return\n",
    "    values = set(ls)\n",
    "    values.remove(max(ls))\n",
    "    values = sorted(values)\n",
    "    for v in values:\n",
    "        yield [min(v, l) for l in ls]\n",
    "\n",
    "\n",
    "def shrink6(ls):\n",
    "    yield from shrink_to_prefix(ls)\n",
    "    yield from delete_individual_elements(ls)\n",
    "    yield from replace_with_simpler(ls)\n",
    "    yield from shrink_shared(ls)\n",
    "    yield from shrink_individual_elements(ls)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "✓ [20, 21, 22, 23, 24, 25, 26]\n",
      "✗ [20]\n",
      "✗ [20, 21]\n",
      "✗ [20, 21, 22, 23]\n",
      "✓ [21, 22, 23, 24, 25, 26]\n",
      "✗ [21]\n",
      "✗ [21, 22]\n",
      "✗ [21, 22, 23, 24]\n",
      "✓ [22, 23, 24, 25, 26]\n",
      "✗ [22]\n",
      "✗ [22, 23]\n",
      "✗ [22, 23, 24, 25]\n",
      "✗ [23, 24, 25, 26]\n",
      "✗ [22, 24, 25, 26]\n",
      "✗ [22, 23, 25, 26]\n",
      "✗ [22, 23, 24, 26]\n",
      "✗ [22, 23, 24, 25]\n",
      "✓ [22, 22, 22, 22, 22]\n",
      "✗ [22]\n",
      "✗ [22, 22]\n",
      "✗ [22, 22, 22, 22]\n",
      "✗ [22, 22, 22, 22]\n",
      "✗ [22, 22, 22, 22]\n",
      "✗ [22, 22, 22, 22]\n",
      "✗ [22, 22, 22, 22]\n",
      "✗ [22, 22, 22, 22]\n",
      "✗ [0, 0, 0, 0, 0]\n",
      "✗ [1, 1, 1, 1, 1]\n",
      "✗ [3, 3, 3, 3, 3]\n",
      "✓ [7, 7, 7, 7, 7]\n",
      "✗ [7]\n",
      "✗ [7, 7]\n",
      "✗ [7, 7, 7, 7]\n",
      "✗ [7, 7, 7, 7]\n",
      "✗ [7, 7, 7, 7]\n",
      "✗ [7, 7, 7, 7]\n",
      "✗ [7, 7, 7, 7]\n",
      "✗ [7, 7, 7, 7]\n",
      "✗ [0, 0, 0, 0, 0]\n",
      "✗ [1, 1, 1, 1, 1]\n",
      "✗ [3, 3, 3, 3, 3]\n",
      "✓ [5, 5, 5, 5, 5]\n",
      "✗ [5]\n",
      "✗ [5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✗ [0, 0, 0, 0, 0]\n",
      "✗ [1, 1, 1, 1, 1]\n",
      "✗ [3, 3, 3, 3, 3]\n",
      "✗ [4, 4, 4, 4, 4]\n",
      "✗ [0, 5, 5, 5, 5]\n",
      "✗ [1, 5, 5, 5, 5]\n",
      "✗ [3, 5, 5, 5, 5]\n",
      "✗ [4, 5, 5, 5, 5]\n",
      "✗ [5, 0, 5, 5, 5]\n",
      "✗ [5, 1, 5, 5, 5]\n",
      "✗ [5, 3, 5, 5, 5]\n",
      "✗ [5, 4, 5, 5, 5]\n",
      "✗ [5, 5, 0, 5, 5]\n",
      "✗ [5, 5, 1, 5, 5]\n",
      "✗ [5, 5, 3, 5, 5]\n",
      "✗ [5, 5, 4, 5, 5]\n",
      "✗ [5, 5, 5, 0, 5]\n",
      "✗ [5, 5, 5, 1, 5]\n",
      "✗ [5, 5, 5, 3, 5]\n",
      "✗ [5, 5, 5, 4, 5]\n",
      "✗ [5, 5, 5, 5, 0]\n",
      "✗ [5, 5, 5, 5, 1]\n",
      "✗ [5, 5, 5, 5, 3]\n",
      "✗ [5, 5, 5, 5, 4]\n",
      "\n",
      "5 shrinks with 73 function calls\n"
     ]
    }
   ],
   "source": [
    "show_trace([20 + i for i in range(7)],\n",
    "           lambda x: len([t for t in x if t >= 5]) >= 5,\n",
    "           partial(greedy_shrink, shrink=shrink6))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we're going to start looking at some numbers.\n",
    "\n",
    "What we'll do is we'll generate 1000 random lists satisfying some predicate, and then simplify them down to the smallest possible examples satisfying those predicates. This lets us verify that these aren't just cherry-picked examples and our methods help in the general case. We fix the set of examples per predicate so that we're comparing like for like.\n",
    "\n",
    "A more proper statistical treatment would probably be a good idea."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from collections import OrderedDict\n",
    "\n",
    "conditions = OrderedDict([\n",
    "    (\"length >= 2\", lambda xs: len(xs) >= 2),\n",
    "    (\"sum >= 500\", lambda xs: sum(xs) >= 500),\n",
    "    (\"sum >= 3\", lambda xs: sum(xs) >= 3),\n",
    "    (\"At least 10 by 5\", lambda xs: len(\n",
    "        [t for t in xs if t >= 5]) >= 10),\n",
    "])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[17861213645196285187,\n",
       " 15609796832515195084,\n",
       " 8808697621832673046,\n",
       " 1013319847337885109,\n",
       " 1252281976438780211,\n",
       " 15526909770962854196,\n",
       " 2065337703776048239,\n",
       " 11654092230944134701,\n",
       " 5554896851708700201,\n",
       " 17485190250805381572,\n",
       " 7700396730246958474,\n",
       " 402840882133605445,\n",
       " 5303116940477413125,\n",
       " 7459257850255946545,\n",
       " 10349184495871650178,\n",
       " 4361155591615075311,\n",
       " 15194020468024244632,\n",
       " 14428821588688846242,\n",
       " 5754975712549869618,\n",
       " 13740966788951413307,\n",
       " 15209704957418077856,\n",
       " 12562588328524673262,\n",
       " 8415556016795311987,\n",
       " 3993098291779210741,\n",
       " 16874756914619597640,\n",
       " 7932421182532982309,\n",
       " 1080869529149674704,\n",
       " 13878842261614060122,\n",
       " 229976195287031921,\n",
       " 8378461140013520338,\n",
       " 6189522326946191255,\n",
       " 16684625600934047114,\n",
       " 12533448641134015292,\n",
       " 10459192142175991903,\n",
       " 15688511015570391481,\n",
       " 3091340728247101611,\n",
       " 4034760776171697910,\n",
       " 6258572097778886531,\n",
       " 13555449085571665140,\n",
       " 6727488149749641424,\n",
       " 7125107819562430884,\n",
       " 1557872425804423698,\n",
       " 4810250441100696888,\n",
       " 10500486959813930693,\n",
       " 841300069403644975,\n",
       " 9278626999406014662,\n",
       " 17219731431761688449,\n",
       " 15650446646901259126,\n",
       " 8683172055034528265,\n",
       " 5138373693056086816,\n",
       " 4055877702343936882,\n",
       " 5696765901584750542,\n",
       " 7133363948804979946,\n",
       " 988518370429658551,\n",
       " 16302597472193523184,\n",
       " 579078764159525857,\n",
       " 10678347012503400890,\n",
       " 8433836779160269996,\n",
       " 13884258181758870664,\n",
       " 13594877609651310055]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "N_EXAMPLES = 1000\n",
    "\n",
    "datasets = {}\n",
    "\n",
    "def gen_list(rnd):\n",
    "    return [\n",
    "        random.getrandbits(64)\n",
    "        for _ in range(random.randint(0, 100))\n",
    "    ]\n",
    "\n",
    "def dataset_for(condition):\n",
    "    if condition in datasets:\n",
    "        return datasets[condition]\n",
    "    constraint = conditions[condition]\n",
    "    dataset = []\n",
    "    rnd = random.Random(condition)\n",
    "    while len(dataset) < N_EXAMPLES:\n",
    "        ls = gen_list(rnd)\n",
    "        if constraint(ls):\n",
    "            dataset.append(ls)\n",
    "    datasets[condition] = dataset\n",
    "    return dataset\n",
    "\n",
    "dataset_for(\"sum >= 3\")[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# In order to avoid run-away cases where things will take basically forever\n",
    "# we cap at 5000 as \"you've taken too long. Stop it\". Because we're only ever\n",
    "# showing the worst case scenario we'll just display this as > 5000 if we ever\n",
    "# hit it and it won't distort statistics.\n",
    "MAX_COUNT = 5000\n",
    "\n",
    "class MaximumCountExceeded(Exception):\n",
    "    pass\n",
    "\n",
    "def call_counts(condition, simplifier):\n",
    "    constraint = conditions[condition]\n",
    "    dataset = dataset_for(condition)\n",
    "    counts = []\n",
    "\n",
    "    for ex in dataset:\n",
    "        counter = [0]\n",
    "    \n",
    "        def run_and_count(ls):\n",
    "            counter[0] += 1\n",
    "            if counter[0] > MAX_COUNT:\n",
    "                raise MaximumCountExceeded()\n",
    "            return constraint(ls)\n",
    "    \n",
    "        try:\n",
    "            simplifier(ex, run_and_count)\n",
    "            counts.extend(counter)\n",
    "        except MaximumCountExceeded:\n",
    "            counts.append(MAX_COUNT + 1)\n",
    "            break\n",
    "    return counts\n",
    "            \n",
    "def worst_case(condition, simplifier):\n",
    "    return max(call_counts(condition, simplifier))\n",
    "\n",
    "worst_case(\n",
    "    \"length >= 2\",\n",
    "    partial(greedy_shrink, shrink=shrink6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from IPython.display import HTML\n",
    "\n",
    "def compare_simplifiers(named_simplifiers):\n",
    "    \"\"\"\n",
    "    Given a list of (name, simplifier) pairs, output a table comparing\n",
    "    the worst case performance of each on our current set of examples.\n",
    "    \"\"\"\n",
    "    html_fragments = []\n",
    "    html_fragments.append(\"<table>\\n<thead>\\n<tr>\")\n",
    "    header = [\"Condition\"]\n",
    "    header.extend(name for name, _ in named_simplifiers)\n",
    "    for h in header:\n",
    "        html_fragments.append(\"<th>%s</th>\" % (h,))\n",
    "    html_fragments.append(\"</tr>\\n</thead>\\n<tbody>\")\n",
    "    \n",
    "    for name in conditions:\n",
    "        bits = [name.replace(\">\", \"&gt;\")]        \n",
    "        for _, simplifier in named_simplifiers:\n",
    "            value = worst_case(name, simplifier)\n",
    "            if value <= MAX_COUNT:\n",
    "                bits.append(str(value))\n",
    "            else:\n",
    "                bits.append(\" &gt; %d\" % (MAX_COUNT,))\n",
    "        html_fragments.append(\"<tr>  \")\n",
    "        html_fragments.append(' '.join(\n",
    "                \"<td>%s</td>\" % (b,) for b in bits))\n",
    "        html_fragments.append(\"</tr>\")\n",
    "    html_fragments.append(\"</tbody>\\n</table>\")\n",
    "    return HTML('\\n'.join(html_fragments))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table>\n",
       "<thead>\n",
       "<tr>\n",
       "<th>Condition</th>\n",
       "<th>2</th>\n",
       "<th>3</th>\n",
       "<th>4</th>\n",
       "<th>5</th>\n",
       "<th>6</th>\n",
       "</tr>\n",
       "</thead>\n",
       "<tbody>\n",
       "<tr>  \n",
       "<td>length &gt;= 2</td> <td>106</td> <td>105</td> <td>13</td> <td>13</td> <td>13</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>sum &gt;= 500</td> <td>1102</td> <td>178</td> <td>80</td> <td>80</td> <td>80</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>sum &gt;= 3</td> <td>108</td> <td>107</td> <td>9</td> <td>9</td> <td>9</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>At least 10 by 5</td> <td>535</td> <td>690</td> <td>809</td> <td>877</td> <td>144</td>\n",
       "</tr>\n",
       "</tbody>\n",
       "</table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compare_simplifiers([\n",
    "   (f.__name__[-1], partial(greedy_shrink, shrink=f))\n",
    "   for f in [shrink2, shrink3, shrink4, shrink5, shrink6]\n",
    "])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So you can see from the above table, the iterations 2 through 5 were a little ambiguous ion that they helped a lot in the cases they were designed to help with but hurt in other cases. 6 however is clearly the best of the lot, being no worse than any of the others on any of the cases and often significantly better.\n",
    "\n",
    "Rather than continuing to refine our shrink further, we instead look to improvements to how we use shrinking. We'll start by noting a simple optimization: If you look at our traces above, we often checked the same example twice. We're only interested in deterministic conditions, so this isn't useful to do. So we'll start by simply pruning out all duplicates. This should have exactly the same set and order of successful shrinks but will avoid a bunch of redundant work."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def greedy_shrink_with_dedupe(ls, constraint, shrink):\n",
    "    seen = set()\n",
    "    while True:\n",
    "        for s in shrink(ls):\n",
    "            key = tuple(s)\n",
    "            if key in seen:\n",
    "                continue\n",
    "            seen.add(key)\n",
    "            if constraint(s):\n",
    "                ls = s\n",
    "                break\n",
    "        else:\n",
    "            return ls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table>\n",
       "<thead>\n",
       "<tr>\n",
       "<th>Condition</th>\n",
       "<th>Normal</th>\n",
       "<th>Deduped</th>\n",
       "</tr>\n",
       "</thead>\n",
       "<tbody>\n",
       "<tr>  \n",
       "<td>length &gt;= 2</td> <td>13</td> <td>6</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>sum &gt;= 500</td> <td>80</td> <td>35</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>sum &gt;= 3</td> <td>9</td> <td>6</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>At least 10 by 5</td> <td>144</td> <td>107</td>\n",
       "</tr>\n",
       "</tbody>\n",
       "</table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compare_simplifiers([\n",
    "   (\"Normal\", partial(greedy_shrink, shrink=shrink6)),\n",
    "   (\"Deduped\", partial(greedy_shrink_with_dedupe,\n",
    "                       shrink=shrink6)),\n",
    "\n",
    "])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As expected, this is a significant improvement in some cases. It is logically impossible that it could ever make things worse, but it's nice that it makes it better.\n",
    "\n",
    "So far we've only looked at things where the interaction between elements was fairly light - the sum cases the values of other elements mattered a bit, but shrinking an integer could never enable other shrinks. Lets look at one where this is not the case: Where our condition is that we have at least 10 distinct elements."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "✓ [100, 101, 102, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [100]\n",
      "✗ [100, 101]\n",
      "✗ [100, 101, 102, 103]\n",
      "✗ [100, 101, 102, 103, 104, 105, 106, 107]\n",
      "✗ [101, 102, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [100, 102, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [100, 101, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [100, 101, 102, 104, 105, 106, 107, 108, 109]\n",
      "✗ [100, 101, 102, 103, 105, 106, 107, 108, 109]\n",
      "✗ [100, 101, 102, 103, 104, 106, 107, 108, 109]\n",
      "✗ [100, 101, 102, 103, 104, 105, 107, 108, 109]\n",
      "✗ [100, 101, 102, 103, 104, 105, 106, 108, 109]\n",
      "✗ [100, 101, 102, 103, 104, 105, 106, 107, 109]\n",
      "✗ [100, 101, 102, 103, 104, 105, 106, 107, 108]\n",
      "✗ [100, 100, 100, 100, 100, 100, 100, 100, 100, 100]\n",
      "✗ [100, 101, 101, 101, 101, 101, 101, 101, 101, 101]\n",
      "✗ [100, 101, 102, 102, 102, 102, 102, 102, 102, 102]\n",
      "✗ [100, 101, 102, 103, 103, 103, 103, 103, 103, 103]\n",
      "✗ [100, 101, 102, 103, 104, 104, 104, 104, 104, 104]\n",
      "✗ [100, 101, 102, 103, 104, 105, 105, 105, 105, 105]\n",
      "✗ [100, 101, 102, 103, 104, 105, 106, 106, 106, 106]\n",
      "✗ [100, 101, 102, 103, 104, 105, 106, 107, 107, 107]\n",
      "✗ [100, 101, 102, 103, 104, 105, 106, 107, 108, 108]\n",
      "✓ [0, 101, 102, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0]\n",
      "✗ [0, 101]\n",
      "✗ [0, 101, 102, 103]\n",
      "✗ [0, 101, 102, 103, 104, 105, 106, 107]\n",
      "✗ [101, 102, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 102, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 101, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 101, 102, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 101, 102, 103, 105, 106, 107, 108, 109]\n",
      "✗ [0, 101, 102, 103, 104, 106, 107, 108, 109]\n",
      "✗ [0, 101, 102, 103, 104, 105, 107, 108, 109]\n",
      "✗ [0, 101, 102, 103, 104, 105, 106, 108, 109]\n",
      "✗ [0, 101, 102, 103, 104, 105, 106, 107, 109]\n",
      "✗ [0, 101, 102, 103, 104, 105, 106, 107, 108]\n",
      "✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
      "✗ [0, 101, 101, 101, 101, 101, 101, 101, 101, 101]\n",
      "✗ [0, 101, 102, 102, 102, 102, 102, 102, 102, 102]\n",
      "✗ [0, 101, 102, 103, 103, 103, 103, 103, 103, 103]\n",
      "✗ [0, 101, 102, 103, 104, 104, 104, 104, 104, 104]\n",
      "✗ [0, 101, 102, 103, 104, 105, 105, 105, 105, 105]\n",
      "✗ [0, 101, 102, 103, 104, 105, 106, 106, 106, 106]\n",
      "✗ [0, 101, 102, 103, 104, 105, 106, 107, 107, 107]\n",
      "✗ [0, 101, 102, 103, 104, 105, 106, 107, 108, 108]\n",
      "✗ [0, 0, 102, 103, 104, 105, 106, 107, 108, 109]\n",
      "✓ [0, 1, 102, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0]\n",
      "✗ [0, 1]\n",
      "✗ [0, 1, 102, 103]\n",
      "✗ [0, 1, 102, 103, 104, 105, 106, 107]\n",
      "✗ [1, 102, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 102, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 102, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 102, 103, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 102, 103, 104, 106, 107, 108, 109]\n",
      "✗ [0, 1, 102, 103, 104, 105, 107, 108, 109]\n",
      "✗ [0, 1, 102, 103, 104, 105, 106, 108, 109]\n",
      "✗ [0, 1, 102, 103, 104, 105, 106, 107, 109]\n",
      "✗ [0, 1, 102, 103, 104, 105, 106, 107, 108]\n",
      "✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
      "✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "✗ [0, 1, 102, 102, 102, 102, 102, 102, 102, 102]\n",
      "✗ [0, 1, 102, 103, 103, 103, 103, 103, 103, 103]\n",
      "✗ [0, 1, 102, 103, 104, 104, 104, 104, 104, 104]\n",
      "✗ [0, 1, 102, 103, 104, 105, 105, 105, 105, 105]\n",
      "✗ [0, 1, 102, 103, 104, 105, 106, 106, 106, 106]\n",
      "✗ [0, 1, 102, 103, 104, 105, 106, 107, 107, 107]\n",
      "✗ [0, 1, 102, 103, 104, 105, 106, 107, 108, 108]\n",
      "✗ [0, 0, 102, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 0, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 1, 103, 104, 105, 106, 107, 108, 109]\n",
      "✓ [0, 1, 3, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0]\n",
      "✗ [0, 1]\n",
      "✗ [0, 1, 3, 103]\n",
      "✗ [0, 1, 3, 103, 104, 105, 106, 107]\n",
      "✗ [1, 3, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 3, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 3, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 3, 103, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 3, 103, 104, 106, 107, 108, 109]\n",
      "✗ [0, 1, 3, 103, 104, 105, 107, 108, 109]\n",
      "✗ [0, 1, 3, 103, 104, 105, 106, 108, 109]\n",
      "✗ [0, 1, 3, 103, 104, 105, 106, 107, 109]\n",
      "✗ [0, 1, 3, 103, 104, 105, 106, 107, 108]\n",
      "✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
      "✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "✗ [0, 1, 3, 3, 3, 3, 3, 3, 3, 3]\n",
      "✗ [0, 1, 3, 103, 103, 103, 103, 103, 103, 103]\n",
      "✗ [0, 1, 3, 103, 104, 104, 104, 104, 104, 104]\n",
      "✗ [0, 1, 3, 103, 104, 105, 105, 105, 105, 105]\n",
      "✗ [0, 1, 3, 103, 104, 105, 106, 106, 106, 106]\n",
      "✗ [0, 1, 3, 103, 104, 105, 106, 107, 107, 107]\n",
      "✗ [0, 1, 3, 103, 104, 105, 106, 107, 108, 108]\n",
      "✗ [0, 0, 3, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 0, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 1, 103, 104, 105, 106, 107, 108, 109]\n",
      "✓ [0, 1, 2, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0]\n",
      "✗ [0, 1]\n",
      "✗ [0, 1, 2, 103]\n",
      "✗ [0, 1, 2, 103, 104, 105, 106, 107]\n",
      "✗ [1, 2, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 2, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 103, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 103, 104, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 103, 104, 105, 107, 108, 109]\n",
      "✗ [0, 1, 2, 103, 104, 105, 106, 108, 109]\n",
      "✗ [0, 1, 2, 103, 104, 105, 106, 107, 109]\n",
      "✗ [0, 1, 2, 103, 104, 105, 106, 107, 108]\n",
      "✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
      "✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✗ [0, 1, 2, 103, 103, 103, 103, 103, 103, 103]\n",
      "✗ [0, 1, 2, 103, 104, 104, 104, 104, 104, 104]\n",
      "✗ [0, 1, 2, 103, 104, 105, 105, 105, 105, 105]\n",
      "✗ [0, 1, 2, 103, 104, 105, 106, 106, 106, 106]\n",
      "✗ [0, 1, 2, 103, 104, 105, 106, 107, 107, 107]\n",
      "✗ [0, 1, 2, 103, 104, 105, 106, 107, 108, 108]\n",
      "✗ [0, 0, 2, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 0, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 1, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 0, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 1, 104, 105, 106, 107, 108, 109]\n",
      "✓ [0, 1, 2, 3, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0]\n",
      "✗ [0, 1]\n",
      "✗ [0, 1, 2, 3]\n",
      "✗ [0, 1, 2, 3, 104, 105, 106, 107]\n",
      "✗ [1, 2, 3, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 2, 3, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 3, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 104, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 104, 105, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 104, 105, 106, 108, 109]\n",
      "✗ [0, 1, 2, 3, 104, 105, 106, 107, 109]\n",
      "✗ [0, 1, 2, 3, 104, 105, 106, 107, 108]\n",
      "✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
      "✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
      "✗ [0, 1, 2, 3, 104, 104, 104, 104, 104, 104]\n",
      "✗ [0, 1, 2, 3, 104, 105, 105, 105, 105, 105]\n",
      "✗ [0, 1, 2, 3, 104, 105, 106, 106, 106, 106]\n",
      "✗ [0, 1, 2, 3, 104, 105, 106, 107, 107, 107]\n",
      "✗ [0, 1, 2, 3, 104, 105, 106, 107, 108, 108]\n",
      "✗ [0, 0, 2, 3, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 0, 3, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 1, 3, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 0, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 1, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 2, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 0, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 1, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 3, 105, 106, 107, 108, 109]\n",
      "✓ [0, 1, 2, 3, 7, 105, 106, 107, 108, 109]\n",
      "✗ [0]\n",
      "✗ [0, 1]\n",
      "✗ [0, 1, 2, 3]\n",
      "✗ [0, 1, 2, 3, 7, 105, 106, 107]\n",
      "✗ [1, 2, 3, 7, 105, 106, 107, 108, 109]\n",
      "✗ [0, 2, 3, 7, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 3, 7, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 7, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 7, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 7, 105, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 7, 105, 106, 108, 109]\n",
      "✗ [0, 1, 2, 3, 7, 105, 106, 107, 109]\n",
      "✗ [0, 1, 2, 3, 7, 105, 106, 107, 108]\n",
      "✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
      "✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
      "✗ [0, 1, 2, 3, 7, 7, 7, 7, 7, 7]\n",
      "✗ [0, 1, 2, 3, 7, 105, 105, 105, 105, 105]\n",
      "✗ [0, 1, 2, 3, 7, 105, 106, 106, 106, 106]\n",
      "✗ [0, 1, 2, 3, 7, 105, 106, 107, 107, 107]\n",
      "✗ [0, 1, 2, 3, 7, 105, 106, 107, 108, 108]\n",
      "✗ [0, 0, 2, 3, 7, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 0, 3, 7, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 1, 3, 7, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 0, 7, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 1, 7, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 2, 7, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 0, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 1, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 3, 105, 106, 107, 108, 109]\n",
      "✓ [0, 1, 2, 3, 5, 105, 106, 107, 108, 109]\n",
      "✗ [0]\n",
      "✗ [0, 1]\n",
      "✗ [0, 1, 2, 3]\n",
      "✗ [0, 1, 2, 3, 5, 105, 106, 107]\n",
      "✗ [1, 2, 3, 5, 105, 106, 107, 108, 109]\n",
      "✗ [0, 2, 3, 5, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 3, 5, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 5, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 5, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 5, 105, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 5, 105, 106, 108, 109]\n",
      "✗ [0, 1, 2, 3, 5, 105, 106, 107, 109]\n",
      "✗ [0, 1, 2, 3, 5, 105, 106, 107, 108]\n",
      "✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
      "✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
      "✗ [0, 1, 2, 3, 5, 5, 5, 5, 5, 5]\n",
      "✗ [0, 1, 2, 3, 5, 105, 105, 105, 105, 105]\n",
      "✗ [0, 1, 2, 3, 5, 105, 106, 106, 106, 106]\n",
      "✗ [0, 1, 2, 3, 5, 105, 106, 107, 107, 107]\n",
      "✗ [0, 1, 2, 3, 5, 105, 106, 107, 108, 108]\n",
      "✗ [0, 0, 2, 3, 5, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 0, 3, 5, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 1, 3, 5, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 0, 5, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 1, 5, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 2, 5, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 0, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 1, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 3, 105, 106, 107, 108, 109]\n",
      "✓ [0, 1, 2, 3, 4, 105, 106, 107, 108, 109]\n",
      "✗ [0]\n",
      "✗ [0, 1]\n",
      "✗ [0, 1, 2, 3]\n",
      "✗ [0, 1, 2, 3, 4, 105, 106, 107]\n",
      "✗ [1, 2, 3, 4, 105, 106, 107, 108, 109]\n",
      "✗ [0, 2, 3, 4, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 3, 4, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 4, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 105, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 105, 106, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 105, 106, 107, 109]\n",
      "✗ [0, 1, 2, 3, 4, 105, 106, 107, 108]\n",
      "✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
      "✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
      "✗ [0, 1, 2, 3, 4, 4, 4, 4, 4, 4]\n",
      "✗ [0, 1, 2, 3, 4, 105, 105, 105, 105, 105]\n",
      "✗ [0, 1, 2, 3, 4, 105, 106, 106, 106, 106]\n",
      "✗ [0, 1, 2, 3, 4, 105, 106, 107, 107, 107]\n",
      "✗ [0, 1, 2, 3, 4, 105, 106, 107, 108, 108]\n",
      "✗ [0, 0, 2, 3, 4, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 0, 3, 4, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 1, 3, 4, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 0, 4, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 1, 4, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 2, 4, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 0, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 1, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 3, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 0, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 1, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 3, 106, 107, 108, 109]\n",
      "✓ [0, 1, 2, 3, 4, 7, 106, 107, 108, 109]\n",
      "✗ [0]\n",
      "✗ [0, 1]\n",
      "✗ [0, 1, 2, 3]\n",
      "✗ [0, 1, 2, 3, 4, 7, 106, 107]\n",
      "✗ [1, 2, 3, 4, 7, 106, 107, 108, 109]\n",
      "✗ [0, 2, 3, 4, 7, 106, 107, 108, 109]\n",
      "✗ [0, 1, 3, 4, 7, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 4, 7, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 7, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 7, 106, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 7, 106, 107, 109]\n",
      "✗ [0, 1, 2, 3, 4, 7, 106, 107, 108]\n",
      "✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
      "✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
      "✗ [0, 1, 2, 3, 4, 4, 4, 4, 4, 4]\n",
      "✗ [0, 1, 2, 3, 4, 7, 7, 7, 7, 7]\n",
      "✗ [0, 1, 2, 3, 4, 7, 106, 106, 106, 106]\n",
      "✗ [0, 1, 2, 3, 4, 7, 106, 107, 107, 107]\n",
      "✗ [0, 1, 2, 3, 4, 7, 106, 107, 108, 108]\n",
      "✗ [0, 0, 2, 3, 4, 7, 106, 107, 108, 109]\n",
      "✗ [0, 1, 0, 3, 4, 7, 106, 107, 108, 109]\n",
      "✗ [0, 1, 1, 3, 4, 7, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 0, 4, 7, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 1, 4, 7, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 2, 4, 7, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 0, 7, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 1, 7, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 3, 7, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 0, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 1, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 3, 106, 107, 108, 109]\n",
      "✓ [0, 1, 2, 3, 4, 5, 106, 107, 108, 109]\n",
      "✗ [0]\n",
      "✗ [0, 1]\n",
      "✗ [0, 1, 2, 3]\n",
      "✗ [0, 1, 2, 3, 4, 5, 106, 107]\n",
      "✗ [1, 2, 3, 4, 5, 106, 107, 108, 109]\n",
      "✗ [0, 2, 3, 4, 5, 106, 107, 108, 109]\n",
      "✗ [0, 1, 3, 4, 5, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 4, 5, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 5, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 106, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 106, 107, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 106, 107, 108]\n",
      "✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
      "✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
      "✗ [0, 1, 2, 3, 4, 4, 4, 4, 4, 4]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 5, 5, 5]\n",
      "✗ [0, 1, 2, 3, 4, 5, 106, 106, 106, 106]\n",
      "✗ [0, 1, 2, 3, 4, 5, 106, 107, 107, 107]\n",
      "✗ [0, 1, 2, 3, 4, 5, 106, 107, 108, 108]\n",
      "✗ [0, 0, 2, 3, 4, 5, 106, 107, 108, 109]\n",
      "✗ [0, 1, 0, 3, 4, 5, 106, 107, 108, 109]\n",
      "✗ [0, 1, 1, 3, 4, 5, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 0, 4, 5, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 1, 4, 5, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 2, 4, 5, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 0, 5, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 1, 5, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 3, 5, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 0, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 1, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 3, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 4, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 0, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 1, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 3, 107, 108, 109]\n",
      "✓ [0, 1, 2, 3, 4, 5, 7, 107, 108, 109]\n",
      "✗ [0]\n",
      "✗ [0, 1]\n",
      "✗ [0, 1, 2, 3]\n",
      "✗ [0, 1, 2, 3, 4, 5, 7, 107]\n",
      "✗ [1, 2, 3, 4, 5, 7, 107, 108, 109]\n",
      "✗ [0, 2, 3, 4, 5, 7, 107, 108, 109]\n",
      "✗ [0, 1, 3, 4, 5, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 4, 5, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 5, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 7, 107, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 7, 107, 108]\n",
      "✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
      "✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
      "✗ [0, 1, 2, 3, 4, 4, 4, 4, 4, 4]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 5, 5, 5]\n",
      "✗ [0, 1, 2, 3, 4, 5, 7, 7, 7, 7]\n",
      "✗ [0, 1, 2, 3, 4, 5, 7, 107, 107, 107]\n",
      "✗ [0, 1, 2, 3, 4, 5, 7, 107, 108, 108]\n",
      "✗ [0, 0, 2, 3, 4, 5, 7, 107, 108, 109]\n",
      "✗ [0, 1, 0, 3, 4, 5, 7, 107, 108, 109]\n",
      "✗ [0, 1, 1, 3, 4, 5, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 0, 4, 5, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 1, 4, 5, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 2, 4, 5, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 0, 5, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 1, 5, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 3, 5, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 0, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 1, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 3, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 4, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 0, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 1, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 3, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 107, 108, 109]\n",
      "✓ [0, 1, 2, 3, 4, 5, 6, 107, 108, 109]\n",
      "✗ [0]\n",
      "✗ [0, 1]\n",
      "✗ [0, 1, 2, 3]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 107]\n",
      "✗ [1, 2, 3, 4, 5, 6, 107, 108, 109]\n",
      "✗ [0, 2, 3, 4, 5, 6, 107, 108, 109]\n",
      "✗ [0, 1, 3, 4, 5, 6, 107, 108, 109]\n",
      "✗ [0, 1, 2, 4, 5, 6, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 5, 6, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 6, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 107, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 107, 108]\n",
      "✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
      "✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
      "✗ [0, 1, 2, 3, 4, 4, 4, 4, 4, 4]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 5, 5, 5]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 6, 6, 6]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 107, 107, 107]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 107, 108, 108]\n",
      "✗ [0, 0, 2, 3, 4, 5, 6, 107, 108, 109]\n",
      "✗ [0, 1, 0, 3, 4, 5, 6, 107, 108, 109]\n",
      "✗ [0, 1, 1, 3, 4, 5, 6, 107, 108, 109]\n",
      "✗ [0, 1, 2, 0, 4, 5, 6, 107, 108, 109]\n",
      "✗ [0, 1, 2, 1, 4, 5, 6, 107, 108, 109]\n",
      "✗ [0, 1, 2, 2, 4, 5, 6, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 0, 5, 6, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 1, 5, 6, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 3, 5, 6, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 0, 6, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 1, 6, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 3, 6, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 4, 6, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 0, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 1, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 3, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 0, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 1, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 3, 108, 109]\n",
      "✓ [0, 1, 2, 3, 4, 5, 6, 7, 108, 109]\n",
      "✗ [0]\n",
      "✗ [0, 1]\n",
      "✗ [0, 1, 2, 3]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7]\n",
      "✗ [1, 2, 3, 4, 5, 6, 7, 108, 109]\n",
      "✗ [0, 2, 3, 4, 5, 6, 7, 108, 109]\n",
      "✗ [0, 1, 3, 4, 5, 6, 7, 108, 109]\n",
      "✗ [0, 1, 2, 4, 5, 6, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 5, 6, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 6, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 108]\n",
      "✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
      "✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
      "✗ [0, 1, 2, 3, 4, 4, 4, 4, 4, 4]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 5, 5, 5]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 6, 6, 6]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 7]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 108, 108]\n",
      "✗ [0, 0, 2, 3, 4, 5, 6, 7, 108, 109]\n",
      "✗ [0, 1, 0, 3, 4, 5, 6, 7, 108, 109]\n",
      "✗ [0, 1, 1, 3, 4, 5, 6, 7, 108, 109]\n",
      "✗ [0, 1, 2, 0, 4, 5, 6, 7, 108, 109]\n",
      "✗ [0, 1, 2, 1, 4, 5, 6, 7, 108, 109]\n",
      "✗ [0, 1, 2, 2, 4, 5, 6, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 0, 5, 6, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 1, 5, 6, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 3, 5, 6, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 0, 6, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 1, 6, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 3, 6, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 4, 6, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 0, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 1, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 3, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 0, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 1, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 3, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 5, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 6, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 0, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 1, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 3, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 109]\n",
      "✓ [0, 1, 2, 3, 4, 5, 6, 7, 15, 109]\n",
      "✗ [0]\n",
      "✗ [0, 1]\n",
      "✗ [0, 1, 2, 3]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7]\n",
      "✗ [1, 2, 3, 4, 5, 6, 7, 15, 109]\n",
      "✗ [0, 2, 3, 4, 5, 6, 7, 15, 109]\n",
      "✗ [0, 1, 3, 4, 5, 6, 7, 15, 109]\n",
      "✗ [0, 1, 2, 4, 5, 6, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 5, 6, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 6, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 15]\n",
      "✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
      "✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
      "✗ [0, 1, 2, 3, 4, 4, 4, 4, 4, 4]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 5, 5, 5]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 6, 6, 6]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 7]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 15, 15]\n",
      "✗ [0, 0, 2, 3, 4, 5, 6, 7, 15, 109]\n",
      "✗ [0, 1, 0, 3, 4, 5, 6, 7, 15, 109]\n",
      "✗ [0, 1, 1, 3, 4, 5, 6, 7, 15, 109]\n",
      "✗ [0, 1, 2, 0, 4, 5, 6, 7, 15, 109]\n",
      "✗ [0, 1, 2, 1, 4, 5, 6, 7, 15, 109]\n",
      "✗ [0, 1, 2, 2, 4, 5, 6, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 0, 5, 6, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 1, 5, 6, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 3, 5, 6, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 0, 6, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 1, 6, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 3, 6, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 4, 6, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 0, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 1, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 3, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 0, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 1, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 3, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 5, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 6, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 0, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 1, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 3, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 109]\n",
      "✓ [0, 1, 2, 3, 4, 5, 6, 7, 11, 109]\n",
      "✗ [0]\n",
      "✗ [0, 1]\n",
      "✗ [0, 1, 2, 3]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7]\n",
      "✗ [1, 2, 3, 4, 5, 6, 7, 11, 109]\n",
      "✗ [0, 2, 3, 4, 5, 6, 7, 11, 109]\n",
      "✗ [0, 1, 3, 4, 5, 6, 7, 11, 109]\n",
      "✗ [0, 1, 2, 4, 5, 6, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 5, 6, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 6, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 11]\n",
      "✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
      "✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
      "✗ [0, 1, 2, 3, 4, 4, 4, 4, 4, 4]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 5, 5, 5]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 6, 6, 6]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 7]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 11, 11]\n",
      "✗ [0, 0, 2, 3, 4, 5, 6, 7, 11, 109]\n",
      "✗ [0, 1, 0, 3, 4, 5, 6, 7, 11, 109]\n",
      "✗ [0, 1, 1, 3, 4, 5, 6, 7, 11, 109]\n",
      "✗ [0, 1, 2, 0, 4, 5, 6, 7, 11, 109]\n",
      "✗ [0, 1, 2, 1, 4, 5, 6, 7, 11, 109]\n",
      "✗ [0, 1, 2, 2, 4, 5, 6, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 0, 5, 6, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 1, 5, 6, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 3, 5, 6, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 0, 6, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 1, 6, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 3, 6, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 4, 6, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 0, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 1, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 3, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 0, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 1, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 3, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 5, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 6, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 0, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 1, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 3, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 109]\n",
      "✓ [0, 1, 2, 3, 4, 5, 6, 7, 9, 109]\n",
      "✗ [0]\n",
      "✗ [0, 1]\n",
      "✗ [0, 1, 2, 3]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7]\n",
      "✗ [1, 2, 3, 4, 5, 6, 7, 9, 109]\n",
      "✗ [0, 2, 3, 4, 5, 6, 7, 9, 109]\n",
      "✗ [0, 1, 3, 4, 5, 6, 7, 9, 109]\n",
      "✗ [0, 1, 2, 4, 5, 6, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 5, 6, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 6, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 9]\n",
      "✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
      "✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
      "✗ [0, 1, 2, 3, 4, 4, 4, 4, 4, 4]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 5, 5, 5]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 6, 6, 6]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 7]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 9, 9]\n",
      "✗ [0, 0, 2, 3, 4, 5, 6, 7, 9, 109]\n",
      "✗ [0, 1, 0, 3, 4, 5, 6, 7, 9, 109]\n",
      "✗ [0, 1, 1, 3, 4, 5, 6, 7, 9, 109]\n",
      "✗ [0, 1, 2, 0, 4, 5, 6, 7, 9, 109]\n",
      "✗ [0, 1, 2, 1, 4, 5, 6, 7, 9, 109]\n",
      "✗ [0, 1, 2, 2, 4, 5, 6, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 0, 5, 6, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 1, 5, 6, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 3, 5, 6, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 0, 6, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 1, 6, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 3, 6, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 4, 6, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 0, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 1, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 3, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 0, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 1, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 3, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 5, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 6, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 0, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 1, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 3, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 109]\n",
      "✓ [0, 1, 2, 3, 4, 5, 6, 7, 8, 109]\n",
      "✗ [0]\n",
      "✗ [0, 1]\n",
      "✗ [0, 1, 2, 3]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7]\n",
      "✗ [1, 2, 3, 4, 5, 6, 7, 8, 109]\n",
      "✗ [0, 2, 3, 4, 5, 6, 7, 8, 109]\n",
      "✗ [0, 1, 3, 4, 5, 6, 7, 8, 109]\n",
      "✗ [0, 1, 2, 4, 5, 6, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 5, 6, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 6, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8]\n",
      "✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
      "✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
      "✗ [0, 1, 2, 3, 4, 4, 4, 4, 4, 4]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 5, 5, 5]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 6, 6, 6]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 7]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 8]\n",
      "✗ [0, 0, 2, 3, 4, 5, 6, 7, 8, 109]\n",
      "✗ [0, 1, 0, 3, 4, 5, 6, 7, 8, 109]\n",
      "✗ [0, 1, 1, 3, 4, 5, 6, 7, 8, 109]\n",
      "✗ [0, 1, 2, 0, 4, 5, 6, 7, 8, 109]\n",
      "✗ [0, 1, 2, 1, 4, 5, 6, 7, 8, 109]\n",
      "✗ [0, 1, 2, 2, 4, 5, 6, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 0, 5, 6, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 1, 5, 6, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 3, 5, 6, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 0, 6, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 1, 6, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 3, 6, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 4, 6, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 0, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 1, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 3, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 0, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 1, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 3, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 5, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 6, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 0, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 1, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 3, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 6, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 0]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 1]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 3]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 7]\n",
      "✓ [0, 1, 2, 3, 4, 5, 6, 7, 8, 15]\n",
      "✗ [0]\n",
      "✗ [0, 1]\n",
      "✗ [0, 1, 2, 3]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7]\n",
      "✗ [1, 2, 3, 4, 5, 6, 7, 8, 15]\n",
      "✗ [0, 2, 3, 4, 5, 6, 7, 8, 15]\n",
      "✗ [0, 1, 3, 4, 5, 6, 7, 8, 15]\n",
      "✗ [0, 1, 2, 4, 5, 6, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 5, 6, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 6, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8]\n",
      "✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
      "✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
      "✗ [0, 1, 2, 3, 4, 4, 4, 4, 4, 4]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 5, 5, 5]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 6, 6, 6]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 7]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 8]\n",
      "✗ [0, 0, 2, 3, 4, 5, 6, 7, 8, 15]\n",
      "✗ [0, 1, 0, 3, 4, 5, 6, 7, 8, 15]\n",
      "✗ [0, 1, 1, 3, 4, 5, 6, 7, 8, 15]\n",
      "✗ [0, 1, 2, 0, 4, 5, 6, 7, 8, 15]\n",
      "✗ [0, 1, 2, 1, 4, 5, 6, 7, 8, 15]\n",
      "✗ [0, 1, 2, 2, 4, 5, 6, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 0, 5, 6, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 1, 5, 6, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 3, 5, 6, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 0, 6, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 1, 6, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 3, 6, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 4, 6, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 0, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 1, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 3, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 0, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 1, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 3, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 5, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 6, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 0, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 1, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 3, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 6, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 0]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 1]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 3]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 7]\n",
      "✓ [0, 1, 2, 3, 4, 5, 6, 7, 8, 11]\n",
      "✗ [0]\n",
      "✗ [0, 1]\n",
      "✗ [0, 1, 2, 3]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7]\n",
      "✗ [1, 2, 3, 4, 5, 6, 7, 8, 11]\n",
      "✗ [0, 2, 3, 4, 5, 6, 7, 8, 11]\n",
      "✗ [0, 1, 3, 4, 5, 6, 7, 8, 11]\n",
      "✗ [0, 1, 2, 4, 5, 6, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 5, 6, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 6, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8]\n",
      "✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
      "✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
      "✗ [0, 1, 2, 3, 4, 4, 4, 4, 4, 4]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 5, 5, 5]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 6, 6, 6]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 7]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 8]\n",
      "✗ [0, 0, 2, 3, 4, 5, 6, 7, 8, 11]\n",
      "✗ [0, 1, 0, 3, 4, 5, 6, 7, 8, 11]\n",
      "✗ [0, 1, 1, 3, 4, 5, 6, 7, 8, 11]\n",
      "✗ [0, 1, 2, 0, 4, 5, 6, 7, 8, 11]\n",
      "✗ [0, 1, 2, 1, 4, 5, 6, 7, 8, 11]\n",
      "✗ [0, 1, 2, 2, 4, 5, 6, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 0, 5, 6, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 1, 5, 6, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 3, 5, 6, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 0, 6, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 1, 6, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 3, 6, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 4, 6, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 0, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 1, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 3, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 0, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 1, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 3, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 5, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 6, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 0, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 1, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 3, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 6, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 0]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 1]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 3]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 7]\n",
      "✓ [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
      "✗ [0]\n",
      "✗ [0, 1]\n",
      "✗ [0, 1, 2, 3]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7]\n",
      "✗ [1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
      "✗ [0, 2, 3, 4, 5, 6, 7, 8, 9]\n",
      "✗ [0, 1, 3, 4, 5, 6, 7, 8, 9]\n",
      "✗ [0, 1, 2, 4, 5, 6, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 5, 6, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 6, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8]\n",
      "✗ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
      "✗ [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "✗ [0, 1, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "✗ [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]\n",
      "✗ [0, 1, 2, 3, 4, 4, 4, 4, 4, 4]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 5, 5, 5]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 6, 6, 6]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 7]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 8]\n",
      "✗ [0, 0, 2, 3, 4, 5, 6, 7, 8, 9]\n",
      "✗ [0, 1, 0, 3, 4, 5, 6, 7, 8, 9]\n",
      "✗ [0, 1, 1, 3, 4, 5, 6, 7, 8, 9]\n",
      "✗ [0, 1, 2, 0, 4, 5, 6, 7, 8, 9]\n",
      "✗ [0, 1, 2, 1, 4, 5, 6, 7, 8, 9]\n",
      "✗ [0, 1, 2, 2, 4, 5, 6, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 0, 5, 6, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 1, 5, 6, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 3, 5, 6, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 0, 6, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 1, 6, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 3, 6, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 4, 6, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 0, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 1, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 3, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 0, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 1, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 3, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 5, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 6, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 0, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 1, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 3, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 6, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 0]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 1]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 3]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 7]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 8]\n",
      "\n",
      "20 shrinks with 848 function calls\n"
     ]
    }
   ],
   "source": [
    "show_trace([100 + i for i in range(10)],\n",
    "           lambda x: len(set(x)) >= 10,\n",
    "           partial(greedy_shrink, shrink=shrink6))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This does not do very well at all.\n",
    "\n",
    "The reason it doesn't is that we keep trying useless shrinks. e.g. none of the shrinks done by shrink\\_to\\_prefix, replace\\_with\\_simpler or shrink\\_shared will ever do anything useful here.\n",
    "\n",
    "So lets switch to an approach where we try shrink types until they stop working and then we move on to the next type:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def multicourse_shrink1(ls, constraint):\n",
    "    seen = set()\n",
    "    for shrink in [\n",
    "        shrink_to_prefix,\n",
    "        replace_with_simpler,\n",
    "        shrink_shared,\n",
    "        shrink_individual_elements,\n",
    "    ]:\n",
    "        while True:\n",
    "            for s in shrink(ls):\n",
    "                key = tuple(s)\n",
    "                if key in seen:\n",
    "                    continue\n",
    "                seen.add(key)\n",
    "                if constraint(s):\n",
    "                    ls = s\n",
    "                    break\n",
    "            else:\n",
    "                break\n",
    "    return ls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "✓ [100, 101, 102, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [100]\n",
      "✗ [100, 101]\n",
      "✗ [100, 101, 102, 103]\n",
      "✗ [100, 101, 102, 103, 104, 105, 106, 107]\n",
      "✗ [100, 100, 100, 100, 100, 100, 100, 100, 100, 100]\n",
      "✗ [100, 101, 101, 101, 101, 101, 101, 101, 101, 101]\n",
      "✗ [100, 101, 102, 102, 102, 102, 102, 102, 102, 102]\n",
      "✗ [100, 101, 102, 103, 103, 103, 103, 103, 103, 103]\n",
      "✗ [100, 101, 102, 103, 104, 104, 104, 104, 104, 104]\n",
      "✗ [100, 101, 102, 103, 104, 105, 105, 105, 105, 105]\n",
      "✗ [100, 101, 102, 103, 104, 105, 106, 106, 106, 106]\n",
      "✗ [100, 101, 102, 103, 104, 105, 106, 107, 107, 107]\n",
      "✗ [100, 101, 102, 103, 104, 105, 106, 107, 108, 108]\n",
      "✓ [0, 101, 102, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 0, 102, 103, 104, 105, 106, 107, 108, 109]\n",
      "✓ [0, 1, 102, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 0, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 1, 103, 104, 105, 106, 107, 108, 109]\n",
      "✓ [0, 1, 3, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 0, 3, 103, 104, 105, 106, 107, 108, 109]\n",
      "✓ [0, 1, 2, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 0, 2, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 0, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 1, 104, 105, 106, 107, 108, 109]\n",
      "✓ [0, 1, 2, 3, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 0, 2, 3, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 0, 3, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 1, 3, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 2, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 0, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 1, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 3, 105, 106, 107, 108, 109]\n",
      "✓ [0, 1, 2, 3, 7, 105, 106, 107, 108, 109]\n",
      "✗ [0, 0, 2, 3, 7, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 0, 3, 7, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 1, 3, 7, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 0, 7, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 1, 7, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 2, 7, 105, 106, 107, 108, 109]\n",
      "✓ [0, 1, 2, 3, 5, 105, 106, 107, 108, 109]\n",
      "✗ [0, 0, 2, 3, 5, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 0, 3, 5, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 1, 3, 5, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 0, 5, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 1, 5, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 2, 5, 105, 106, 107, 108, 109]\n",
      "✓ [0, 1, 2, 3, 4, 105, 106, 107, 108, 109]\n",
      "✗ [0, 0, 2, 3, 4, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 0, 3, 4, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 1, 3, 4, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 0, 4, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 1, 4, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 2, 4, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 0, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 1, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 3, 106, 107, 108, 109]\n",
      "✓ [0, 1, 2, 3, 4, 7, 106, 107, 108, 109]\n",
      "✗ [0, 0, 2, 3, 4, 7, 106, 107, 108, 109]\n",
      "✗ [0, 1, 0, 3, 4, 7, 106, 107, 108, 109]\n",
      "✗ [0, 1, 1, 3, 4, 7, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 0, 4, 7, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 1, 4, 7, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 2, 4, 7, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 0, 7, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 1, 7, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 3, 7, 106, 107, 108, 109]\n",
      "✓ [0, 1, 2, 3, 4, 5, 106, 107, 108, 109]\n",
      "✗ [0, 0, 2, 3, 4, 5, 106, 107, 108, 109]\n",
      "✗ [0, 1, 0, 3, 4, 5, 106, 107, 108, 109]\n",
      "✗ [0, 1, 1, 3, 4, 5, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 0, 4, 5, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 1, 4, 5, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 2, 4, 5, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 0, 5, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 1, 5, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 3, 5, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 4, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 0, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 1, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 3, 107, 108, 109]\n",
      "✓ [0, 1, 2, 3, 4, 5, 7, 107, 108, 109]\n",
      "✗ [0, 0, 2, 3, 4, 5, 7, 107, 108, 109]\n",
      "✗ [0, 1, 0, 3, 4, 5, 7, 107, 108, 109]\n",
      "✗ [0, 1, 1, 3, 4, 5, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 0, 4, 5, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 1, 4, 5, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 2, 4, 5, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 0, 5, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 1, 5, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 3, 5, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 0, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 1, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 3, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 4, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 107, 108, 109]\n",
      "✓ [0, 1, 2, 3, 4, 5, 6, 107, 108, 109]\n",
      "✗ [0, 0, 2, 3, 4, 5, 6, 107, 108, 109]\n",
      "✗ [0, 1, 0, 3, 4, 5, 6, 107, 108, 109]\n",
      "✗ [0, 1, 1, 3, 4, 5, 6, 107, 108, 109]\n",
      "✗ [0, 1, 2, 0, 4, 5, 6, 107, 108, 109]\n",
      "✗ [0, 1, 2, 1, 4, 5, 6, 107, 108, 109]\n",
      "✗ [0, 1, 2, 2, 4, 5, 6, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 0, 5, 6, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 1, 5, 6, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 3, 5, 6, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 0, 6, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 1, 6, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 3, 6, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 4, 6, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 0, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 1, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 3, 108, 109]\n",
      "✓ [0, 1, 2, 3, 4, 5, 6, 7, 108, 109]\n",
      "✗ [0, 0, 2, 3, 4, 5, 6, 7, 108, 109]\n",
      "✗ [0, 1, 0, 3, 4, 5, 6, 7, 108, 109]\n",
      "✗ [0, 1, 1, 3, 4, 5, 6, 7, 108, 109]\n",
      "✗ [0, 1, 2, 0, 4, 5, 6, 7, 108, 109]\n",
      "✗ [0, 1, 2, 1, 4, 5, 6, 7, 108, 109]\n",
      "✗ [0, 1, 2, 2, 4, 5, 6, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 0, 5, 6, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 1, 5, 6, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 3, 5, 6, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 0, 6, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 1, 6, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 3, 6, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 4, 6, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 0, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 1, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 3, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 5, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 6, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 0, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 1, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 3, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 109]\n",
      "✓ [0, 1, 2, 3, 4, 5, 6, 7, 15, 109]\n",
      "✗ [0, 0, 2, 3, 4, 5, 6, 7, 15, 109]\n",
      "✗ [0, 1, 0, 3, 4, 5, 6, 7, 15, 109]\n",
      "✗ [0, 1, 1, 3, 4, 5, 6, 7, 15, 109]\n",
      "✗ [0, 1, 2, 0, 4, 5, 6, 7, 15, 109]\n",
      "✗ [0, 1, 2, 1, 4, 5, 6, 7, 15, 109]\n",
      "✗ [0, 1, 2, 2, 4, 5, 6, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 0, 5, 6, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 1, 5, 6, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 3, 5, 6, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 0, 6, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 1, 6, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 3, 6, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 4, 6, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 0, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 1, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 3, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 7, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 0, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 1, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 3, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 5, 15, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 6, 15, 109]\n",
      "✓ [0, 1, 2, 3, 4, 5, 6, 7, 11, 109]\n",
      "✗ [0, 0, 2, 3, 4, 5, 6, 7, 11, 109]\n",
      "✗ [0, 1, 0, 3, 4, 5, 6, 7, 11, 109]\n",
      "✗ [0, 1, 1, 3, 4, 5, 6, 7, 11, 109]\n",
      "✗ [0, 1, 2, 0, 4, 5, 6, 7, 11, 109]\n",
      "✗ [0, 1, 2, 1, 4, 5, 6, 7, 11, 109]\n",
      "✗ [0, 1, 2, 2, 4, 5, 6, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 0, 5, 6, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 1, 5, 6, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 3, 5, 6, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 0, 6, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 1, 6, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 3, 6, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 4, 6, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 0, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 1, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 3, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 7, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 0, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 1, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 3, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 5, 11, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 6, 11, 109]\n",
      "✓ [0, 1, 2, 3, 4, 5, 6, 7, 9, 109]\n",
      "✗ [0, 0, 2, 3, 4, 5, 6, 7, 9, 109]\n",
      "✗ [0, 1, 0, 3, 4, 5, 6, 7, 9, 109]\n",
      "✗ [0, 1, 1, 3, 4, 5, 6, 7, 9, 109]\n",
      "✗ [0, 1, 2, 0, 4, 5, 6, 7, 9, 109]\n",
      "✗ [0, 1, 2, 1, 4, 5, 6, 7, 9, 109]\n",
      "✗ [0, 1, 2, 2, 4, 5, 6, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 0, 5, 6, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 1, 5, 6, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 3, 5, 6, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 0, 6, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 1, 6, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 3, 6, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 4, 6, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 0, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 1, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 3, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 7, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 0, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 1, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 3, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 5, 9, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 6, 9, 109]\n",
      "✓ [0, 1, 2, 3, 4, 5, 6, 7, 8, 109]\n",
      "✗ [0, 0, 2, 3, 4, 5, 6, 7, 8, 109]\n",
      "✗ [0, 1, 0, 3, 4, 5, 6, 7, 8, 109]\n",
      "✗ [0, 1, 1, 3, 4, 5, 6, 7, 8, 109]\n",
      "✗ [0, 1, 2, 0, 4, 5, 6, 7, 8, 109]\n",
      "✗ [0, 1, 2, 1, 4, 5, 6, 7, 8, 109]\n",
      "✗ [0, 1, 2, 2, 4, 5, 6, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 0, 5, 6, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 1, 5, 6, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 3, 5, 6, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 0, 6, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 1, 6, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 3, 6, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 4, 6, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 0, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 1, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 3, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 0, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 1, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 3, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 5, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 6, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 6, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 0]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 1]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 3]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 7]\n",
      "✓ [0, 1, 2, 3, 4, 5, 6, 7, 8, 15]\n",
      "✗ [0, 0, 2, 3, 4, 5, 6, 7, 8, 15]\n",
      "✗ [0, 1, 0, 3, 4, 5, 6, 7, 8, 15]\n",
      "✗ [0, 1, 1, 3, 4, 5, 6, 7, 8, 15]\n",
      "✗ [0, 1, 2, 0, 4, 5, 6, 7, 8, 15]\n",
      "✗ [0, 1, 2, 1, 4, 5, 6, 7, 8, 15]\n",
      "✗ [0, 1, 2, 2, 4, 5, 6, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 0, 5, 6, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 1, 5, 6, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 3, 5, 6, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 0, 6, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 1, 6, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 3, 6, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 4, 6, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 0, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 1, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 3, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 7, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 0, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 1, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 3, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 5, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 6, 8, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 0, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 1, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 3, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 6, 15]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 15]\n",
      "✓ [0, 1, 2, 3, 4, 5, 6, 7, 8, 11]\n",
      "✗ [0, 0, 2, 3, 4, 5, 6, 7, 8, 11]\n",
      "✗ [0, 1, 0, 3, 4, 5, 6, 7, 8, 11]\n",
      "✗ [0, 1, 1, 3, 4, 5, 6, 7, 8, 11]\n",
      "✗ [0, 1, 2, 0, 4, 5, 6, 7, 8, 11]\n",
      "✗ [0, 1, 2, 1, 4, 5, 6, 7, 8, 11]\n",
      "✗ [0, 1, 2, 2, 4, 5, 6, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 0, 5, 6, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 1, 5, 6, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 3, 5, 6, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 0, 6, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 1, 6, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 3, 6, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 4, 6, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 0, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 1, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 3, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 7, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 0, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 1, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 3, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 5, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 6, 8, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 0, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 1, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 3, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 6, 11]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 11]\n",
      "✓ [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
      "✗ [0, 0, 2, 3, 4, 5, 6, 7, 8, 9]\n",
      "✗ [0, 1, 0, 3, 4, 5, 6, 7, 8, 9]\n",
      "✗ [0, 1, 1, 3, 4, 5, 6, 7, 8, 9]\n",
      "✗ [0, 1, 2, 0, 4, 5, 6, 7, 8, 9]\n",
      "✗ [0, 1, 2, 1, 4, 5, 6, 7, 8, 9]\n",
      "✗ [0, 1, 2, 2, 4, 5, 6, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 0, 5, 6, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 1, 5, 6, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 3, 5, 6, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 0, 6, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 1, 6, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 3, 6, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 4, 6, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 0, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 1, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 3, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 0, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 1, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 3, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 5, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 6, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 0, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 1, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 3, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 6, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 8]\n",
      "\n",
      "20 shrinks with 318 function calls\n"
     ]
    }
   ],
   "source": [
    "show_trace([100 + i for i in range(10)],\n",
    "           lambda x: len(set(x)) >= 10,\n",
    "           multicourse_shrink1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "conditions[\"10 distinct elements\"] = lambda xs: len(set(xs)) >= 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table>\n",
       "<thead>\n",
       "<tr>\n",
       "<th>Condition</th>\n",
       "<th>Single pass</th>\n",
       "<th>Multi pass</th>\n",
       "</tr>\n",
       "</thead>\n",
       "<tbody>\n",
       "<tr>  \n",
       "<td>length &gt;= 2</td> <td>6</td> <td>4</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>sum &gt;= 500</td> <td>35</td> <td>34</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>sum &gt;= 3</td> <td>6</td> <td>5</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>At least 10 by 5</td> <td>107</td> <td>58</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>10 distinct elements</td> <td>623</td> <td>320</td>\n",
       "</tr>\n",
       "</tbody>\n",
       "</table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compare_simplifiers([\n",
    "    (\"Single pass\", partial(greedy_shrink_with_dedupe,\n",
    "                            shrink=shrink6)),\n",
    "    (\"Multi pass\", multicourse_shrink1)\n",
    "])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So that helped, but not as much as we'd have liked. It's saved us about half the calls, when really we wanted to save 90% of the calls.\n",
    "\n",
    "We're on the right track though. The problem is not that our solution isn't good, it's that it didn't go far enough: We're *still* making an awful lot of useless calls. The problem is that each time we shrink the element at index i we try shrinking the elements at indexes 0 through i - 1, and this will never work. So what we want to do is to break shrinking elements into a separate shrinker for each index:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def simplify_index(i):\n",
    "    def accept(ls):\n",
    "        if i >= len(ls):\n",
    "            return\n",
    "        for v in shrink_integer(ls[i]):\n",
    "            s = list(ls)\n",
    "            s[i] = v\n",
    "            yield s\n",
    "    return accept\n",
    "\n",
    "def shrinkers_for(ls):\n",
    "    yield shrink_to_prefix\n",
    "    yield delete_individual_elements\n",
    "    yield replace_with_simpler\n",
    "    yield shrink_shared\n",
    "    for i in range(len(ls)):\n",
    "        yield simplify_index(i)\n",
    "\n",
    "def multicourse_shrink2(ls, constraint):\n",
    "    seen = set()\n",
    "    for shrink in shrinkers_for(ls):\n",
    "        while True:\n",
    "            for s in shrink(ls):\n",
    "                key = tuple(s)\n",
    "                if key in seen:\n",
    "                    continue\n",
    "                seen.add(key)\n",
    "                if constraint(s):\n",
    "                    ls = s\n",
    "                    break\n",
    "            else:\n",
    "                break\n",
    "    return ls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "✓ [100, 101, 102, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [100]\n",
      "✗ [100, 101]\n",
      "✗ [100, 101, 102, 103]\n",
      "✗ [100, 101, 102, 103, 104, 105, 106, 107]\n",
      "✗ [101, 102, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [100, 102, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [100, 101, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [100, 101, 102, 104, 105, 106, 107, 108, 109]\n",
      "✗ [100, 101, 102, 103, 105, 106, 107, 108, 109]\n",
      "✗ [100, 101, 102, 103, 104, 106, 107, 108, 109]\n",
      "✗ [100, 101, 102, 103, 104, 105, 107, 108, 109]\n",
      "✗ [100, 101, 102, 103, 104, 105, 106, 108, 109]\n",
      "✗ [100, 101, 102, 103, 104, 105, 106, 107, 109]\n",
      "✗ [100, 101, 102, 103, 104, 105, 106, 107, 108]\n",
      "✗ [100, 100, 100, 100, 100, 100, 100, 100, 100, 100]\n",
      "✗ [100, 101, 101, 101, 101, 101, 101, 101, 101, 101]\n",
      "✗ [100, 101, 102, 102, 102, 102, 102, 102, 102, 102]\n",
      "✗ [100, 101, 102, 103, 103, 103, 103, 103, 103, 103]\n",
      "✗ [100, 101, 102, 103, 104, 104, 104, 104, 104, 104]\n",
      "✗ [100, 101, 102, 103, 104, 105, 105, 105, 105, 105]\n",
      "✗ [100, 101, 102, 103, 104, 105, 106, 106, 106, 106]\n",
      "✗ [100, 101, 102, 103, 104, 105, 106, 107, 107, 107]\n",
      "✗ [100, 101, 102, 103, 104, 105, 106, 107, 108, 108]\n",
      "✓ [0, 101, 102, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 0, 102, 103, 104, 105, 106, 107, 108, 109]\n",
      "✓ [0, 1, 102, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 0, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 1, 103, 104, 105, 106, 107, 108, 109]\n",
      "✓ [0, 1, 3, 103, 104, 105, 106, 107, 108, 109]\n",
      "✓ [0, 1, 2, 103, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 0, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 1, 104, 105, 106, 107, 108, 109]\n",
      "✓ [0, 1, 2, 3, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 2, 104, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 0, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 1, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 3, 105, 106, 107, 108, 109]\n",
      "✓ [0, 1, 2, 3, 7, 105, 106, 107, 108, 109]\n",
      "✓ [0, 1, 2, 3, 5, 105, 106, 107, 108, 109]\n",
      "✓ [0, 1, 2, 3, 4, 105, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 0, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 1, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 3, 106, 107, 108, 109]\n",
      "✓ [0, 1, 2, 3, 4, 7, 106, 107, 108, 109]\n",
      "✓ [0, 1, 2, 3, 4, 5, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 4, 106, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 0, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 1, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 3, 107, 108, 109]\n",
      "✓ [0, 1, 2, 3, 4, 5, 7, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 5, 107, 108, 109]\n",
      "✓ [0, 1, 2, 3, 4, 5, 6, 107, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 0, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 1, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 3, 108, 109]\n",
      "✓ [0, 1, 2, 3, 4, 5, 6, 7, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 5, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 6, 108, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 0, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 1, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 3, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 7, 109]\n",
      "✓ [0, 1, 2, 3, 4, 5, 6, 7, 15, 109]\n",
      "✓ [0, 1, 2, 3, 4, 5, 6, 7, 11, 109]\n",
      "✓ [0, 1, 2, 3, 4, 5, 6, 7, 9, 109]\n",
      "✓ [0, 1, 2, 3, 4, 5, 6, 7, 8, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 6, 109]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 0]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 1]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 3]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 7]\n",
      "✓ [0, 1, 2, 3, 4, 5, 6, 7, 8, 15]\n",
      "✓ [0, 1, 2, 3, 4, 5, 6, 7, 8, 11]\n",
      "✓ [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
      "✗ [0, 1, 2, 3, 4, 5, 6, 7, 8, 8]\n",
      "\n",
      "20 shrinks with 75 function calls\n"
     ]
    }
   ],
   "source": [
    "show_trace([100 + i for i in range(10)],\n",
    "           lambda x: len(set(x)) >= 10,\n",
    "           multicourse_shrink2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This worked great! It saved us a huge number of function calls.\n",
    "\n",
    "Unfortunately it's wrong. Actually the previous one was wrong too, but this one is more obviously wrong. The problem is that shrinking later elements can unlock more shrinks for earlier elements and we'll never be able to benefit from that here:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "✓ [101, 100]\n",
      "✗ [101]\n",
      "✗ [100]\n",
      "✗ [100, 100]\n",
      "✗ [0, 100]\n",
      "✗ [1, 100]\n",
      "✗ [3, 100]\n",
      "✗ [7, 100]\n",
      "✗ [15, 100]\n",
      "✗ [31, 100]\n",
      "✗ [63, 100]\n",
      "✗ [82, 100]\n",
      "✗ [91, 100]\n",
      "✗ [96, 100]\n",
      "✗ [98, 100]\n",
      "✗ [99, 100]\n",
      "✓ [101, 0]\n",
      "\n",
      "1 shrinks with 16 function calls\n"
     ]
    }
   ],
   "source": [
    "show_trace([101, 100],\n",
    "           lambda x: len(x) >= 2 and x[0] > x[1],\n",
    "           multicourse_shrink2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Armed with this example we can also show an example where the previous one is wrong because a later simplification unlocks an earlier one because shrinking values allows us to delete more elements:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "✓ [5, 5, 5, 5, 5, 5, 5, 5, 5, 5]\n",
      "✗ [5]\n",
      "✗ [5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✓ [5, 5, 5, 5, 5, 5, 5, 5]\n",
      "✓ [0, 0, 0, 0, 0, 0, 0, 0]\n",
      "\n",
      "2 shrinks with 5 function calls\n"
     ]
    }
   ],
   "source": [
    "show_trace([5] * 10,\n",
    "           lambda x: x and len(x) > max(x),\n",
    "           multicourse_shrink1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "conditions[\"First > Second\"] = lambda xs: len(xs) >= 2 and xs[0] > xs[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Note: We modify this to mask off the high bits because otherwise the probability of\n",
    "# hitting the condition at random is too low.\n",
    "conditions[\"Size > max & 63\"] = lambda xs: xs and len(xs) > (max(xs) & 63)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So what we'll try doing is iterating this to a fixed point and see what happens:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def multicourse_shrink3(ls, constraint):\n",
    "    seen = set()\n",
    "    while True:\n",
    "        old_ls = ls\n",
    "        for shrink in shrinkers_for(ls):\n",
    "            while True:\n",
    "                for s in shrink(ls):\n",
    "                    key = tuple(s)\n",
    "                    if key in seen:\n",
    "                        continue\n",
    "                    seen.add(key)\n",
    "                    if constraint(s):\n",
    "                        ls = s\n",
    "                        break\n",
    "                else:\n",
    "                    break\n",
    "        if ls == old_ls:\n",
    "            return ls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "✓ [101, 100]\n",
      "✗ [101]\n",
      "✗ [100]\n",
      "✗ [100, 100]\n",
      "✗ [0, 100]\n",
      "✗ [1, 100]\n",
      "✗ [3, 100]\n",
      "✗ [7, 100]\n",
      "✗ [15, 100]\n",
      "✗ [31, 100]\n",
      "✗ [63, 100]\n",
      "✗ [82, 100]\n",
      "✗ [91, 100]\n",
      "✗ [96, 100]\n",
      "✗ [98, 100]\n",
      "✗ [99, 100]\n",
      "✓ [101, 0]\n",
      "✗ [0]\n",
      "✗ [0, 0]\n",
      "✓ [1, 0]\n",
      "✗ [1]\n",
      "\n",
      "2 shrinks with 20 function calls\n"
     ]
    }
   ],
   "source": [
    "show_trace([101, 100],\n",
    "           lambda xs: len(xs) >= 2 and xs[0] > xs[1],\n",
    "           multicourse_shrink3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "✓ [5, 5, 5, 5, 5, 5, 5, 5, 5, 5]\n",
      "✗ [5]\n",
      "✗ [5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✓ [5, 5, 5, 5, 5, 5, 5, 5]\n",
      "✓ [5, 5, 5, 5, 5, 5, 5]\n",
      "✓ [5, 5, 5, 5, 5, 5]\n",
      "✗ [5, 5, 5, 5, 5]\n",
      "✓ [0, 0, 0, 0, 0, 0]\n",
      "✓ [0]\n",
      "✗ []\n",
      "\n",
      "5 shrinks with 10 function calls\n"
     ]
    }
   ],
   "source": [
    "show_trace([5] * 10,\n",
    "           lambda x: x and len(x) > max(x),\n",
    "           multicourse_shrink3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So that worked. Yay!\n",
    "\n",
    "Lets compare how this does to our single pass implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table>\n",
       "<thead>\n",
       "<tr>\n",
       "<th>Condition</th>\n",
       "<th>Single pass</th>\n",
       "<th>Multi pass</th>\n",
       "</tr>\n",
       "</thead>\n",
       "<tbody>\n",
       "<tr>  \n",
       "<td>length &gt;= 2</td> <td>6</td> <td>6</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>sum &gt;= 500</td> <td>35</td> <td>35</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>sum &gt;= 3</td> <td>6</td> <td>6</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>At least 10 by 5</td> <td>107</td> <td>73</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>10 distinct elements</td> <td>623</td> <td>131</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>First &gt; Second</td> <td>1481</td> <td>1445</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>Size &gt; max & 63</td> <td>600</td> <td> &gt; 5000</td>\n",
       "</tr>\n",
       "</tbody>\n",
       "</table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compare_simplifiers([\n",
    "    (\"Single pass\", partial(greedy_shrink_with_dedupe,\n",
    "                            shrink=shrink6)),\n",
    "    (\"Multi pass\", multicourse_shrink3)\n",
    "    \n",
    "])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So the answer is generally favourably but *ouch* that last one.\n",
    "\n",
    "What's happening there is that because later shrinks are opening up potentially very large improvements accessible to the lower shrinks, the original greedy algorithm can exploit that much better, while the multi pass algorithm spends a lot of time in the later stages with their incremental shrinks.\n",
    "\n",
    "Lets see another similar example before we try to fix this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import hashlib\n",
    "\n",
    "conditions[\"Messy\"] = lambda xs: hashlib.md5(repr(xs).encode('utf-8')).hexdigest()[0] == '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table>\n",
       "<thead>\n",
       "<tr>\n",
       "<th>Condition</th>\n",
       "<th>Single pass</th>\n",
       "<th>Multi pass</th>\n",
       "</tr>\n",
       "</thead>\n",
       "<tbody>\n",
       "<tr>  \n",
       "<td>length &gt;= 2</td> <td>6</td> <td>6</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>sum &gt;= 500</td> <td>35</td> <td>35</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>sum &gt;= 3</td> <td>6</td> <td>6</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>At least 10 by 5</td> <td>107</td> <td>73</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>10 distinct elements</td> <td>623</td> <td>131</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>First &gt; Second</td> <td>1481</td> <td>1445</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>Size &gt; max & 63</td> <td>600</td> <td> &gt; 5000</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>Messy</td> <td>1032</td> <td> &gt; 5000</td>\n",
       "</tr>\n",
       "</tbody>\n",
       "</table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compare_simplifiers([\n",
    "    (\"Single pass\", partial(greedy_shrink_with_dedupe,\n",
    "                            shrink=shrink6)),\n",
    "    (\"Multi pass\", multicourse_shrink3)\n",
    "    \n",
    "])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This one is a bit different in that the problem is not that the structure is one we're ill suited to exploiting, it's that there is no structure at all so we have no hope of exploiting it. Literally any change at all will unlock earlier shrinks we could have done.\n",
    "\n",
    "What we're going to try to do is hybridize the two approaches. If we notice we're performing an awful lot of shrinks we can take that as a hint that we should be trying again from earlier stages.\n",
    "\n",
    "Here is our first approach. We simply restart the whole process every five shrinks:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "MAX_SHRINKS_PER_RUN = 2\n",
    "\n",
    "\n",
    "def multicourse_shrink4(ls, constraint):\n",
    "    seen = set()\n",
    "    while True:\n",
    "        old_ls = ls\n",
    "        shrinks_this_run = 0\n",
    "        for shrink in shrinkers_for(ls):\n",
    "            while shrinks_this_run < MAX_SHRINKS_PER_RUN:\n",
    "                for s in shrink(ls):\n",
    "                    key = tuple(s)\n",
    "                    if key in seen:\n",
    "                        continue\n",
    "                    seen.add(key)\n",
    "                    if constraint(s):\n",
    "                        shrinks_this_run += 1\n",
    "                        ls = s\n",
    "                        break\n",
    "                else:\n",
    "                    break\n",
    "        if ls == old_ls:\n",
    "            return ls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table>\n",
       "<thead>\n",
       "<tr>\n",
       "<th>Condition</th>\n",
       "<th>Single pass</th>\n",
       "<th>Multi pass</th>\n",
       "<th>Multi pass with restart</th>\n",
       "</tr>\n",
       "</thead>\n",
       "<tbody>\n",
       "<tr>  \n",
       "<td>length &gt;= 2</td> <td>6</td> <td>6</td> <td>6</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>sum &gt;= 500</td> <td>35</td> <td>35</td> <td>35</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>sum &gt;= 3</td> <td>6</td> <td>6</td> <td>6</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>At least 10 by 5</td> <td>107</td> <td>73</td> <td>90</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>10 distinct elements</td> <td>623</td> <td>131</td> <td>396</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>First &gt; Second</td> <td>1481</td> <td>1445</td> <td>1463</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>Size &gt; max & 63</td> <td>600</td> <td> &gt; 5000</td> <td> &gt; 5000</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>Messy</td> <td>1032</td> <td> &gt; 5000</td> <td>1423</td>\n",
       "</tr>\n",
       "</tbody>\n",
       "</table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compare_simplifiers([\n",
    "    (\"Single pass\", partial(greedy_shrink_with_dedupe,\n",
    "                            shrink=shrink6)),\n",
    "    (\"Multi pass\", multicourse_shrink3),\n",
    "    (\"Multi pass with restart\", multicourse_shrink4)    \n",
    "    \n",
    "])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That works OK, but it's pretty unsatisfying as it loses us most of the benefits of the multi pass shrinking - we're now at most twice as good as the greedy one.\n",
    "\n",
    "So what we're going to do is bet on the multi pass working and then gradually degrade to the greedy algorithm as it fails to work."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def multicourse_shrink5(ls, constraint):\n",
    "    seen = set()\n",
    "    max_shrinks_per_run = 10\n",
    "    while True:\n",
    "        shrinks_this_run = 0\n",
    "        for shrink in shrinkers_for(ls):\n",
    "            while shrinks_this_run < max_shrinks_per_run:\n",
    "                for s in shrink(ls):\n",
    "                    key = tuple(s)\n",
    "                    if key in seen:\n",
    "                        continue\n",
    "                    seen.add(key)\n",
    "                    if constraint(s):\n",
    "                        shrinks_this_run += 1\n",
    "                        ls = s\n",
    "                        break\n",
    "                else:\n",
    "                    break\n",
    "        if max_shrinks_per_run > 1:\n",
    "            max_shrinks_per_run -= 2\n",
    "        if not shrinks_this_run:\n",
    "            return ls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "✓ [5, 5, 5, 5, 5, 5, 5, 5, 5, 5]\n",
      "✗ [5]\n",
      "✗ [5, 5]\n",
      "✗ [5, 5, 5, 5]\n",
      "✓ [5, 5, 5, 5, 5, 5, 5, 5]\n",
      "✓ [5, 5, 5, 5, 5, 5, 5]\n",
      "✓ [5, 5, 5, 5, 5, 5]\n",
      "✗ [5, 5, 5, 5, 5]\n",
      "✓ [0, 0, 0, 0, 0, 0]\n",
      "✓ [0]\n",
      "✗ []\n",
      "\n",
      "5 shrinks with 10 function calls\n"
     ]
    }
   ],
   "source": [
    "show_trace([5] * 10,\n",
    "           lambda x: x and len(x) > max(x),\n",
    "           multicourse_shrink5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table>\n",
       "<thead>\n",
       "<tr>\n",
       "<th>Condition</th>\n",
       "<th>Single pass</th>\n",
       "<th>Multi pass</th>\n",
       "<th>Multi pass with restart</th>\n",
       "<th>Multi pass with variable restart</th>\n",
       "</tr>\n",
       "</thead>\n",
       "<tbody>\n",
       "<tr>  \n",
       "<td>length &gt;= 2</td> <td>6</td> <td>6</td> <td>6</td> <td>6</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>sum &gt;= 500</td> <td>35</td> <td>35</td> <td>35</td> <td>35</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>sum &gt;= 3</td> <td>6</td> <td>6</td> <td>6</td> <td>6</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>At least 10 by 5</td> <td>107</td> <td>73</td> <td>90</td> <td>73</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>10 distinct elements</td> <td>623</td> <td>131</td> <td>396</td> <td>212</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>First &gt; Second</td> <td>1481</td> <td>1445</td> <td>1463</td> <td>1168</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>Size &gt; max & 63</td> <td>600</td> <td> &gt; 5000</td> <td> &gt; 5000</td> <td>1002</td>\n",
       "</tr>\n",
       "<tr>  \n",
       "<td>Messy</td> <td>1032</td> <td> &gt; 5000</td> <td>1423</td> <td>824</td>\n",
       "</tr>\n",
       "</tbody>\n",
       "</table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compare_simplifiers([\n",
    "    (\"Single pass\", partial(greedy_shrink_with_dedupe,\n",
    "                            shrink=shrink6)),\n",
    "    (\"Multi pass\", multicourse_shrink3),        \n",
    "    (\"Multi pass with restart\", multicourse_shrink4),\n",
    "    (\"Multi pass with variable restart\", multicourse_shrink5)   \n",
    "])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is now more or less the current state of the art (it's actually a bit different from the Hypothesis state of the art at the time of this writing. I'm planning to merge some of the things I figured out in the course of writing this back in). We've got something that is able to adaptively take advantage of structure where it is present, but degrades reasonably gracefully back to the more aggressive version that works better in unstructured examples.\n",
    "\n",
    "Surprisingly, on some examples it seems to even be best of all of them. I think that's more coincidence than truth though."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
